题目描述

Description

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.
题目大意：求解子树第k大 输出第k大的权值的点的标号

Input

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)

Output

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.

Sample Input

5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2

Sample Output

5
4
5
5

题目分析

询问子树第k大
我们对序维护主席树 因为序是连续的那么查询就变成了
并且我们对于每颗线段树的节点还要维护点的标号

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot;
int head[100010],to[300010],net[300010];
void add(int x,int y)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y;
}
int size[100010],color;
struct your
{
    int lson,rson;
    int size,val;
}a[100010*35];
int root[100010],number,num[100010],val[100010];
void update(int x,int &y,int l,int r,int c,int w)
{
    y=++number;
    a[y]=a[x],a[y].size++;
    if(l==r)
    {   
        a[y].val=w; 
        return ;
    }
    int mid=(l+r)>>1;
    if(c<=mid) update(a[x].lson,a[y].lson,l,mid,c,w);
    else update(a[x].rson,a[y].rson,mid+1,r,c,w);
}
int ask(int x,int y,int l,int r,int k)
{
    if(l==r) return a[y].val;
    int mid=(l+r)>>1;
    int temp=a[a[y].lson].size-a[a[x].lson].size;
    if(temp>=k) return ask(a[x].lson,a[y].lson,l,mid,k);
    else return ask(a[x].rson,a[y].rson,mid+1,r,k-temp);
}
void dfs(int x,int temp)
{
    color++;
    update(root[color-1],root[color],1,1000000010,val[x],x);
    num[x]=color,size[x]=1;
    for(int i=head[x];i;i=net[i])
        if(to[i]!=temp) dfs(to[i],x),size[x]+=size[to[i]];
}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]),val[i]++;
    for(int x,y,i=1;i<n;i++) 
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0);
    scanf("%d",&m);
    for(int x,k,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&k);
        printf("%d\n",ask(root[num[x]-1],root[num[x]+size[x]-1],1,1000000010,k));
    }
    return 0;
}