树上主席树。
我靠这是第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=0,kr[maxv]; int ls[maxv*18],rs[maxv*18],root[maxv],tot=0,sum[maxv*18]; int w[maxv],cnt=0,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+1,b+n+1); len=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+len+1,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]=0; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,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]+1; if (left==right) return; int mid=(left+right)>>1; if (pos<=mid) modify(ls[last],ls[now],left,mid,pos); else modify(rs[last],rs[now],mid+1,right,pos); } int ask(int last,int now,int left,int right,int x) { if (left==right) return left; int mid=(left+right)>>1; 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+1,right,x-r); } int main() { memset(g,0,sizeof(g)); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } divide(); dfs(1,1); build(root[0],1,len); scanf("%d",&q); for (int i=1;i<=n;i++) modify(root[i-1],root[i],1,len,a[fw[i]]); for (int i=1;i<=q;i++) { scanf("%d%d",&x,&y); printf("%d ",kr[ask(root[w[x]-1],root[mx[x]],1,len,y)]); } return 0; }