Description
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.
Input
The first line contains one integer n (1 <= n <= 10^5). 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 <= 10^4) 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)
Output
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.
按dfs序建可持久化线段树，子树对应连续的区间，可以直接查询kth
#include<cstdio>
inline int _int(){
int x=,c=getchar();
while(c>||c<)c=getchar();
while(c>&&c<)x=x*+c-,c=getchar();
return x;
}
const int N=;
int n;
int v[N],rt[N],id[N],idr[N],idp=;
int es[N*],enx[N*],e0[N],ep=;
int ch[N*][],sz[N*],ids[N*],p=;
int ins(int w,int x,int id){
int u=++p,u0=u;
for(int i=;~i;i--){
int d=x>>i&;
ch[u][d^]=ch[w][d^];
sz[u=ch[u][d]=++p]=sz[w=ch[w][d]]+;
}
ids[u]=id;
return u0;
}
void dfs(int w,int pa){
id[w]=++idp;
rt[idp]=ins(rt[idp-],v[w],w);
for(int i=e0[w];i;i=enx[i]){
int u=es[i];
if(u!=pa)dfs(u,w);
}
idr[w]=idp;
}
void kth(int w1,int w2,int k){
for(int i=;~i;i--){
int s=sz[ch[w1][]]-sz[ch[w2][]];
if(s<k){
k-=s;
w1=ch[w1][];
w2=ch[w2][];
}else{
w1=ch[w1][];
w2=ch[w2][];
}
}
printf("%d\n",ids[w1]);
}
int main(){
n=_int();
for(int i=;i<=n;i++)v[i]=_int();
for(int i=;i<n;i++){
int a=_int(),b=_int();
es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;
}
dfs(,);
for(int q=_int();q;q--){
int x=_int();
kth(rt[idr[x]],rt[id[x]-],_int());
}
return ;
}