求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
map<int,int> mp;
struct Node
{
	int v;
	int l,r;
}t[N<<8];
int a[N];
int dfn[N];
int rt[N<<2];
int cnt;
int lsh[N<<2];
int tot;
int n,m;
int node[N<<2];
vector<int> G[N];
int siz[N];
void dfs(int x,int fa)
{
	siz[x]++;
	dfn[x]=++cnt;
	for(int v:G[x])
	{
		if(v!=fa) 
		{
			siz[x]+=siz[v];
			dfs(v,x);
		}
	}
	return;
}
int query(int o1,int o2,int l,int r,int q)
{
	if(l==r) return l;
	int mid=l+r>>1;
	int tmp=t[t[o2].l].v-t[t[o1].l].v; 
	if(tmp>=q) return query(t[o1].l,t[o2].l,l,mid,q);
	return query(t[o1].r,t[o2].r,mid+1,r,q-tmp);
}
void pushup(int o)
{
	t[o].v=t[t[o].l].v+t[t[o].r].v;
}
void change(int lsto,int &o,int l,int r,int q,int v)
{
	if(!o) o=++cnt;
	if(l==r)
	{
		t[o].v+=v;
		return;	
	} 
	int mid=l+r>>1;
	if(q<=mid)
	{
		t[o].r=t[lsto].r;
		t[o].l=++cnt;
		t[t[o].l]=t[t[lsto].l];
		change(t[lsto].l,t[o].l,l,mid,q,v);
	}
	else
	{
		t[o].l=t[lsto].l;
		t[o].r=++cnt;
		t[t[o].r]=t[t[lsto].r];
		change(t[lsto].r,t[o].r,mid+1,r,q,v);
	}
	pushup(o);
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		mp[a[i]]=i;
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%lld%lld",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,-1);
	cnt=0;
	for(int i=1;i<=n;i++)
	{
		//cout<<i<<" : "<<dfn[i]<<endl;
		node[dfn[i]]=a[i];
		lsh[dfn[i]]=node[dfn[i]];
	}
	sort(lsh+1,lsh+n+1);
	tot=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++)
	{
		node[i]=lower_bound(lsh+1,lsh+tot+1,node[i])-lsh;
		change(rt[i-1],rt[i],1,tot,node[i],1);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,q;
		scanf("%lld%lld",&l,&q);
		printf("%lld\n",mp[lsh[query(rt[dfn[l]-1],rt[dfn[l]+siz[l]-1],1,tot,q)]]);
	}
	return 0;
}