题意：给定一颗树。询问一个子树中第k大的节点。

【终于在0:02的时候A掉了=。=】

这几天复习一下数据结构。先复习POJ2104。写可持久化线段树练手先。

然后到了这道题。其实也蛮裸的。

先求出dfs序。记录每个节点开始和结束的时间戳。然后就相当于每个点开始到结束这个区间里求第2*k大。

然后就是一个主席树了。

根据JC大神的指点结束的时间戳不用占位置了，根据下一个开始的时间戳减一就行。这样可以省一半的空间，也可以省很多时间。

由于spoj太慢加了一个read。后来一不小心就A了。速度还行吧。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int w[200010],lc[2100010],rc[4100010],bin[100010],p[200010],n1[200010],h[100010],ee=0,tot;
int id[100010],sum[2100010],T[100010],num[100010],begin[100010],end[100010],n,c=0;
void read(int &x){
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-48;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}void dfs(int u,int fa){
	num[begin[u]=++c]=w[u];
	for(int i=h[u];~i;i=n1[i])	if(p[i]!=fa)	dfs(p[i],u);
	end[u]=c;
}void build(int l,int r,int &rt){
	rt=++tot;	sum[rt]=0;	if(l==r)	return;	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
}void modify(int p,int v,int l,int r,int &rt){
	rt=++tot;	sum[rt]=sum[p]+1;	lc[rt]=lc[p];	rc[rt]=rc[p];	
	if(l==r)	return;	int m=l+r>>1;
	if(v<=m)	modify(lc[p],v,l,m,lc[rt]);
	else		modify(rc[p],v,m+1,r,rc[rt]);
}int ask(int L,int R,int l,int r,int k){
	if(l==r)	return l;	int cnt=sum[lc[R]]-sum[lc[L]],m=l+r>>1;
	if(k<=cnt)	return ask(lc[L],lc[R],l,m,k);
	else		return ask(rc[L],rc[R],m+1,r,k-cnt);
}int main(){
	read(n);	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)	read(w[i]),bin[i]=w[i];
	sort(bin+1,bin+n+1);
	int x,y;
	for(int i=1;i<=n;i++){	w[i]=lower_bound(bin+1,bin+n+1,w[i])-bin;id[w[i]]=i;}
	for(int i=1;i<n;i++)	read(x),read(y),ae(x,y);
	dfs(1,0);	build(1,n,T[0]);
	for(int i=1;i<=n;i++)	modify(T[i-1],num[i],1,n,T[i]);
	int	q;	read(q);
	while(q--){
		read(x);read(y);
		printf("%d\n",id[ask(T[begin[x]-1],T[end[x]],1,n,y)]);
	}return 0;
}

• 相关文章