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 <= 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)

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.

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

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100050

#define maxn n

int head[N],to[N<<1],nxt[N<<1],cnt,n,m,S[N],dfn[N],root[N],t[N*30],ls[N*30],rs[N*30],tot,val[N],son[N],rr[N];

inline void add(int u,int v) {

    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

struct A {

    int num,id,v;

}a[N];

bool cmp1(const A &x,const A &y){return x.num<y.num;}

bool cmp2(const A &x,const A &y){return x.id<y.id;}

void dfs(int x,int y) {

    int i;

    S[++S[0]]=x; dfn[x]=S[0];

    for(i=head[x];i;i=nxt[i]) {

        if(to[i]!=y) {

            dfs(to[i],x);

        }

    }

    son[x]=S[0];

}

void insert(int &y,int x,int l,int r,int v) {

    y=++tot; t[y]=t[x]+1;

    if(l==r) return ;

    int mid=(l+r)>>1;

    if(v<=mid) rs[y]=rs[x],insert(ls[y],ls[x],l,mid,v);

    else ls[y]=ls[x],insert(rs[y],rs[x],mid+1,r,v);

}

int query(int x,int y,int l,int r,int k) {

    if(l==r) return l;

    int mid=(l+r)>>1,sizls=t[ls[x]]-t[ls[y]];

    if(k<=sizls) return query(ls[x],ls[y],l,mid,k);

    else return query(rs[x],rs[y],mid+1,r,k-sizls);

}

int main() {

    scanf("%d",&n);

    int i,x,y,k;

    for(i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].id=i;

    sort(a+1,a+n+1,cmp1);

    int j=0;a[0].num=43345;

    for(i=1;i<=n;i++) {

        if(a[i].num!=a[i-1].num) j++;

        a[i].v=j; rr[j]=a[i].id;

    }

    sort(a+1,a+n+1,cmp2);

    for(i=1;i<n;i++) {

        scanf("%d%d",&x,&y); add(x,y); add(y,x);

    }

    dfs(1,0);

    for(i=1;i<=n;i++) {

        insert(root[i],root[i-1],0,maxn,a[S[i]].v);

    }

    scanf("%d",&m);

    while(m--) {

        scanf("%d%d",&x,&k);

        printf("%d\n",rr[query(root[son[x]],root[dfn[x]-1],0,maxn,k)]);

    }

}