SPOJ 1487. Query on a tree III

SPOJ Problem Set (classical) SPOJ 1487. Query on a tree III Problem code: PT07J
 
 
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.
Input
The first line contains one integer n (1 <= n <= 105). 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 <= 104) which denotes the number of the queries. Each line of the nextm 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.
Example

Input:

5

1 3 5 2 7

1 2

2 3

1 4

3 5

4

2 3

4 1

3 2

3 2



Output:

5

4

5

5
---------------------------------------------------------------
    ：          K    。
    ：   dfs        ，               ，         k  ，        。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

#define MID(x,y) ( ( x + y ) >> 1 )

#define L(x) ( x << 1 )

#define R(x) ( x << 1 | 1 )

#define BUG puts("here!!!")

#define LL long long

using namespace std;



const int N=100005;

int n,m;

int val[40][N],sorted[N],toleft[40][N];

bool cmp(int a,int b)

{

    return a<b;

}

struct node

{

    int l,r;

    int getmid()

    {

        return (l+r)>>1;

    }

} tree[N * 4];

void build(int rt,int l,int r,int d)

{

    tree[rt].l=l;

    tree[rt].r=r;

    if(l==r) return;

    int mid=(l+r) >> 1;

    int same=mid-l+1;

    for(int i=l; i<=r; ++i)

        if (val[d][i]<sorted[mid])same--;

    int lpos=l;

    int rpos=mid+1;

    for(int i=l; i<=r; ++i)

    {

        if(i==l)toleft[d][i]=0;

        else toleft[d][i]=toleft[d][i - 1];

        if(val[d][i]<sorted[mid])

        {

            toleft[d][i]++;

            val[d+1][lpos++]=val[d][i];

        }

        else if(val[d][i]>sorted[mid])val[d+1][rpos++]=val[d][i];

        else if(same)

        {

            same--;

            toleft[d][i]++;

            val[d+1][lpos++]=val[d][i];

        }

        else val[d+1][rpos++]=val[d][i];

    }

    build(L(rt),l,mid,d+1);

    build(R(rt),mid+1,r,d+1);

}

int query(int rt, int l, int r, int d, int k)

{

    if(l==r)return val[d][l];

    int s,ss;

    if(l==tree[rt].l)

    {

        s=toleft[d][r];

        ss=0;

    }

    else

    {

        s=toleft[d][r]-toleft[d][l-1];

        ss=toleft[d][l-1];

    }

    if(k<=s)

    {

        int left=tree[rt].l+ss;

        int right=left+s-1;

        return query(L(rt),left,right,d+1,k);

    }

    else

    {

        int b=l-tree[rt].l-ss;

        int left=tree[rt].getmid()+b+1;

        int right=left+r-l-s;

        return query(R(rt),left,right,d+1,k-s);

    }

}



int lab[N],one[N],two[N],eid,num;

int head[N],ed[N<<1],nxt[N<<1];

map<int,int>ha;



void addedge(int s,int e)

{

    ed[eid]=e;

    nxt[eid]=head[s];

    head[s]=eid++;

}



void dfs(int s,int f)

{

    one[s]=num;

    sorted[num]=lab[s];

    val[0][num++]=lab[s];

    for(int i=head[s]; ~i; i=nxt[i])

        if(ed[i]!=f)dfs(ed[i],s);

    two[s]=num-1;

}



int main()

{

//    freopen("/home/axorb/in","r",stdin);

    ha.clear();

    scanf("%d",&n);

    eid=0;

    memset(head,-1,sizeof(head));

    for(int i=1; i<=n; i++)

    {

        scanf("%d",&lab[i]);

        ha[lab[i]]=i;

    }

    for(int i=1; i<n; i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    num=0;

    dfs(1,-1);

sort(sorted,sorted+n,cmp);

build(1,0,n-1,0);

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        printf("%d
",ha[query(1,one[a],two[a],0,b)]);

    }

}