题意翻译
你被给定一棵带点权的n个点的有根数，点从1到n编号。
定义查询 query(x,k): 寻找以x为根的k大点的编号（从小到大排序第k个点）
假设没有两个相同的点权。
输入格式： 第一行为整数n，第二行为点权，接下来n-1行为树边，接下来一行为整数m，下面m行为两个整数x,k，代表query(x,k)
输出格式： m行，输出每次查询的结果。
Translated by @vegacx
题目描述
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}5 ). The next line contains n integers _l {i}i (0 <= _l {i}i <= 10 ^{9}9 ) 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}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.
输入输出样例
输入样例#1：
5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2
输出样例#1：
5
4
5
5
Solution
这道题,直接维护一遍树上的DFS序,然后记录每个节点 siz,再用主席树维护即可。
然后查询的时候查询 ( b[i] , b[i]+siz[i]-1 ) ,需要注意的是输出的是编号。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct sj{int to,next;}line[maxn*2];
int size,n,m,num,q,siz[maxn];
int head[maxn],id[maxn],tot,idx[maxn];
int a[maxn],b[maxn],c[maxn],T[maxn];
int L[maxn*20],R[maxn*20],sum[maxn*20];
void add(int x,int y)
{
line[++size].to=y;
line[size].next=head[x];
head[x]=size;
}
int old[maxn];
void dfs(int x)
{
siz[x]=1;
a[++num]=c[x];
id[x]=num; b[num]=a[num];
old[num]=x;
for(int i=head[x];i;i=line[i].next)
{
int tt=line[i].to;
if(!siz[tt])
{
dfs(tt);
siz[x]+=siz[tt];
}
}
}
int build(int l,int r)
{
int rt=++tot;
if(l!=r)
{
int mid=(l+r)/2;
L[rt]=build(l,mid);
R[rt]=build(mid+1,r);
}
return rt;
}
int update(int pre,int l,int r,int x)
{
int rt=++tot;
L[rt]=L[pre];
R[rt]=R[pre];
sum[rt]=sum[pre]+1;
int mid=(l+r)/2;
if(l!=r)
{
if (x<=mid) L[rt]=update(L[pre],l,mid,x);
else R[rt]=update(R[pre],mid+1,r,x);
}
return rt;
}
int query(int x,int y,int l,int r,int k)
{
if(l==r)return l;
int now=sum[L[y]]-sum[L[x]];
int mid=(l+r)/2;
if(now>=k) return query(L[x],L[y],l,mid,k);
else return query(R[x],R[y],mid+1,r,k-now);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<n;i++)
{
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1);
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
T[0]=build(1,m);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+1+m,a[i])-b,
T[i]=update(T[i-1],1,m,a[i]);
idx[a[i]]=old[i];
}
scanf("%d",&q);
while(q--)
{
int x,k;
scanf("%d%d",&x,&k);
int p=query(T[id[x]-1],T[id[x]+siz[x]-1],1,m,k);
printf("%d
",idx[p]);
}
}
/*
5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2
*/