2017-12-12

Query on a tree III

You are given a node-labeled rooted tree with n nodes.
Define the query (x, k): Find the node whose label is k-th largest in the subtree of the node x. Assume no two nodes have the same labels.
The first line contains one integer n (1 <= n <= 105). The next line contains n integers li (0 <= li <= 109) which denotes the label of the i-th node.
Each line of the following n - 1 lines contains two integers u, v. They denote there is an edge between node u and node v. Node 1 is the root of the tree.

The next line contains one integer m (1 <= m <= 104) which denotes the number of the queries. Each line of the next m contains two integers x, k. (k <= the total node number in the subtree of x)

For each query (x, k), output the index of the node whose label is the k-th largest in the subtree of the node x.

Input:

5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2

Output:

5
4
5
5

Solution

查询第k大就是主席树裸体
然后这个就是查询子树第k大
那不就是 dfs序上查询即可？

#include <bits/stdc++.h>
using namespace std;
#define maxn (int)(1e5+10)
#define LL long long
inline int read(){
	int rtn=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))rtn=(rtn<<1)+(rtn<<3)+ch-'0',ch=getchar();
	return rtn*f;
}
int n,m,cnt,p[maxn],w[maxn],dfn[maxn],root[maxn],size[maxn],coc,num,sz;
struct node{
	int a,b,nt;
}e[maxn<<2];
struct HJT{
	int ls,rs,cnt,id;
}T[maxn*60];
inline void add(int x,int y){
	e[++cnt].a=x;e[cnt].b=y;
	e[cnt].nt=p[x];p[x]=cnt;
}
inline void insert(int &p,int l,int r,int q,int v){
	T[++sz]=T[p];p=sz;
	if(l==r)return void((T[p].cnt=1)&&(T[p].id=v));
	int mid=l+r>>1;
	if(q<=mid)insert(T[p].ls,l,mid,q,v);
	else if(q>mid)insert(T[p].rs,mid+1,r,q,v);
	T[p].cnt=T[T[p].ls].cnt+T[T[p].rs].cnt;
}
inline int query(int lp,int rp,int l,int r,int k){
	if(l==r)return T[rp].id;
	int s=T[T[rp].ls].cnt-T[T[lp].ls].cnt;
	int mid=l+r>>1;
	if(k<=s)return query(T[lp].ls,T[rp].ls,l,mid,k);
	else return query(T[lp].rs,T[rp].rs,mid+1,r,k-s); 
}
inline void dfs(int x){
	size[x]=1;dfn[x]=++coc;
	root[coc]=root[coc-1];
	insert(root[coc],0,1e9,w[x],x);
	for(int i=p[x];i;i=e[i].nt){
		int k=e[i].b;
		if(size[k])continue;
		dfs(k);size[x]+=size[k];
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	dfs(1);
	m=read();
	while(m--){
		int x=read(),k=read();
		printf("%d\n",query(root[dfn[x]-1],root[dfn[x]+size[x]-1],0,1e9,k));
	}
	return 0;
}