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 4 5 5

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=100010;

int n,m,cnt,tot;

int to[maxn<<1],next[maxn<<1],head[maxn],v[maxn],p[maxn],q[maxn],rt[maxn];

int ls[maxn*30],rs[maxn*30],siz[maxn*30],s[maxn*30];

struct number

{

    int val,org;

}num[maxn];

bool cmp(number a,number b)

{

    return a.val<b.val;

}

void insert(int x,int &y,int l,int r,int a,int b)

{

    if(l>r)  return ;

    y=++tot,siz[y]=siz[x]+1;

    if(l==r)

    {

        s[y]=b;

        return ;

    }

    int mid=l+r>>1;

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

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

}

int query(int a,int b,int l,int r,int c)

{

    if(l==r)    return s[a];

    int mid=l+r>>1,sm=siz[ls[a]]-siz[ls[b]];

    if(c<=sm)    return query(ls[a],ls[b],l,mid,c);

    else    return query(rs[a],rs[b],mid+1,r,c-sm);

}

void dfs(int x,int fa)

{

    p[x]=++p[0];

    insert(rt[p[0]-1],rt[p[0]],1,n,v[x],x);

    for(int i=head[x];i!=-1;i=next[i])  if(to[i]!=fa)   dfs(to[i],x);

    q[x]=p[0];

}

void add(int a,int b)

{

    to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

int main()

{

    scanf("%d",&n);

    int i,a,b;

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

    sort(num+1,num+n+1,cmp);

    for(i=1;i<=n;i++)    v[num[i].org]=i;

    memset(head,-1,sizeof(head));

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

    {

        scanf("%d%d",&a,&b);

        add(a,b),add(b,a);

    }

    dfs(1,0);

    scanf("%d",&m);

    for(i=1;i<=m;i++)

    {

        scanf("%d%d",&a,&b);

        printf("%d\n",query(rt[q[a]],rt[p[a]-1],1,n,b));

    }

    return 0;

}