树上主席树。
我靠这是第k小吧。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 200050
#define maxe 300500
using namespace std;
int n,a[maxv],b[maxv],len,x,y,g[maxv],q,nume=,kr[maxv];
int ls[maxv*],rs[maxv*],root[maxv],tot=,sum[maxv*];
int w[maxv],cnt=,mx[maxv],fw[maxv];
struct edge
{
int v,nxt;
}e[maxe];
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void divide()
{
sort(b+,b+n+);
len=unique(b+,b+n+)-b-;
for (int i=;i<=n;i++)
{
a[i]=lower_bound(b+,b+len+,a[i])-b;
kr[a[i]]=i;
}
}
void dfs(int x,int fath)
{
w[x]=mx[x]=++cnt;fw[cnt]=x;
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v!=fath)
{
dfs(v,x);
mx[x]=max(mx[x],mx[v]);
}
}
}
void build(int &now,int left,int right)
{
now=++tot;sum[now]=;
if (left==right) return;
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
return;
}
void modify(int last,int &now,int left,int right,int pos)
{
now=++tot;
ls[now]=ls[last];rs[now]=rs[last];sum[now]=sum[last]+;
if (left==right) return;
int mid=(left+right)>>;
if (pos<=mid) modify(ls[last],ls[now],left,mid,pos);
else modify(rs[last],rs[now],mid+,right,pos);
}
int ask(int last,int now,int left,int right,int x)
{
if (left==right) return left;
int mid=(left+right)>>;
int r=sum[ls[now]]-sum[ls[last]];
if (x<=r) return ask(ls[last],ls[now],left,mid,x);
else return ask(rs[last],rs[now],mid+,right,x-r);
}
int main()
{
memset(g,,sizeof(g));
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
for (int i=;i<=n-;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
divide();
dfs(,);
build(root[],,len);
scanf("%d",&q);
for (int i=;i<=n;i++)
modify(root[i-],root[i],,len,a[fw[i]]);
for (int i=;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",kr[ask(root[w[x]-],root[mx[x]],,len,y)]);
}
return ;
}