题目描述
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 1 3 5 2 7 1 2 2 3 1 4 3 5 4 2 3 4 1 3 2 3 2
样例输出
5 4 5 5
题目大意
给出一棵以1为根的树，每个点有一个点权。多次询问每个点为根的子树中权值第k小的点是哪个
题解
DFS序+主席树
我也不知道为什么k-th largest number是第k小的意思。反正第k小既能解释样例又能A题。
维护一个DFS序，然后子树就转化为一段连续的区间，我们要求区间第k小。
直接裸上主席树即可。
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
int w[N] , s[N] , r[N] , head[N] , to[N << 1] , nxt[N << 1] , cnt , pos[N] , v[N] , last[N] , tot , root[N] , ls[N * 18] , rs[N * 18] , si[N * 18] , num;
void add(int x , int y)
{
to[++cnt] = y , nxt[cnt] = head[x] , head[x] = cnt;
}
void dfs(int x , int fa)
{
int i;
pos[x] = ++tot , v[tot] = w[x];
for(i = head[x] ; i ; i = nxt[i]) if(to[i] != fa) dfs(to[i] , x);
last[x] = tot;
}
void ins(int p , int l , int r , int x , int &y)
{
y = ++num , si[y] = si[x] + 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) rs[y] = rs[x] , ins(p , l , mid , ls[x] , ls[y]);
else ls[y] = ls[x] , ins(p , mid + 1 , r , rs[x] , rs[y]);
}
int query(int k , int l , int r , int x , int y)
{
if(l == r) return l;
int mid = (l + r) >> 1;
if(k <= si[ls[y]] - si[ls[x]]) return query(k , l , mid , ls[x] , ls[y]);
else return query(k - si[ls[y]] + si[ls[x]] , mid + 1 , r , rs[x] , rs[y]);
}
int main()
{
int n , m , i , x , y;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , s[i] = w[i];
sort(s + 1 , s + n + 1);
for(i = 1 ; i <= n ; i ++ ) w[i] = lower_bound(s + 1 , s + n + 1 , w[i]) - s , r[w[i]] = i;
for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
dfs(1 , 0);
for(i = 1 ; i <= n ; i ++ ) ins(v[i] , 1 , n , root[i - 1] , root[i]);
scanf("%d" , &m);
while(m -- ) scanf("%d%d" , &x , &y) , printf("%d\n" , r[query(y , 1 , n , root[pos[x] - 1] , root[last[x]])]);
return 0;
}