题意

你被给定一棵带点权的n个点的有根数，点从1到n编号。

定义查询 query(x,k): 寻找以x为根的k大点的编号（从小到大排序第k个点）

假设没有两个相同的点权。

输入格式： 第一行为整数n，第二行为点权，接下来n-1行为树边，接下来一行为整数m，下面m行为两个整数x,k，代表query(x,k)

输出格式： m行，输出每次查询的结果。

题解

先一遍dfs，然后建个主席树，带上去直接跑一跑就好了

我忘了注意dfs序的位置和原来的编号……结果调了半天啥都调不出来……

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 char obuf[1<<24],*o=obuf;19 inline void print(int x){20     if(x>9) print(x/10);21     *o++=x%10+48;22 }23 const int N=100005,M=N*30;24 int sum[M],L[M],R[M],rt[N];25 int ver[N<<1],Next[N<<1],head[N];26 int ls[N],rs[N],a[N],b[N],id[N],pos[N];27 int n,m,cnt,tot,q;28 void update(int last,int &now,int l,int r,int x){29     sum[now=++cnt]=sum[last]+1;30     if(l==r) return;31     int mid=(l+r)>>1;32     if(x<=mid) R[now]=R[last],update(L[last],L[now],l,mid,x);33     else L[now]=L[last],update(R[last],R[now],mid+1,r,x);34 }35 int query(int u,int v,int l,int r,int k){36     if(l>=r) return l;37     int x=sum[L[v]]-sum[L[u]];38     int mid=(l+r)>>1;39     if(x>=k) return query(L[u],L[v],l,mid,k);40     else return query(R[u],R[v],mid+1,r,k-x);41 }42 inline void add(int u,int v){43     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;44     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;45 }46 void dfs(int u,int fa){47     a[ls[u]=++m]=b[u],id[m]=u;48     for(int i=head[u];i;i=Next[i])49     if(ver[i]!=fa) dfs(ver[i],u);50     rs[u]=m;51 }52 int main(){53     //freopen("testdata.in","r",stdin);54     n=read();55     for(int i=1;i<=n;++i) b[i]=read();56     for(int i=1;i