BZOJ1803: Spoj1487 Query on a tree III

1803: Spoj1487 Query on a tree III

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 286 Solved: 125
[Submit][Status]

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.

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大呢，人与人之间的信任呢。。。

子树查询 dfs序+主席树搞掉。。。

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 200000+5
 26 
 27 #define maxm 3000000+5
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 struct edge{int go,next;}e[2*maxn];
 61 int n,m,cnt,tot,a[maxn],b[maxn],c[maxn],d[maxn],rt[maxn],ls[maxm],rs[maxm],s[maxm];
 62 int head[maxn],l[maxn],r[maxn],t[maxn][2];
 63 inline void insert(int x,int y)
 64 {
 65     e[++tot]=(edge){y,head[x]};head[x]=tot;
 66     e[++tot]=(edge){x,head[y]};head[y]=tot;
 67 }
 68 inline bool cmp(int x,int y){return a[x]<a[y];}
 69 inline void update(int l,int r,int x,int &y,int z)
 70 {
 71     y=++cnt;
 72     s[y]=s[x]+1;
 73     if(l==r)return;
 74     ls[y]=ls[x];rs[y]=rs[x];
 75     int mid=(l+r)>>1;
 76     if(z<=mid)update(l,mid,ls[x],ls[y],z);else update(mid+1,r,rs[x],rs[y],z);
 77 }
 78 inline void dfs(int x,int f)
 79 {
 80     t[x][0]=++m;
 81     update(1,n,rt[m-1],rt[m],c[x]);
 82     for(int i=head[x];i;i=e[i].next)if(e[i].go!=f)dfs(e[i].go,x);
 83     t[x][1]=m;
 84 }
 85 
 86 int main()
 87 
 88 {
 89 
 90     freopen("input.txt","r",stdin);
 91 
 92     freopen("output.txt","w",stdout);
 93 
 94     n=read();
 95     for1(i,n)a[i]=read(),b[i]=i;
 96     sort(b+1,b+n+1,cmp);
 97     for1(i,n)c[b[i]]=i;
 98     for1(i,n-1)insert(read(),read());
 99     dfs(1,0);
100     m=read();
101     while(m--)
102     {
103         int x=read(),k=read(),l=1,r=n,xx=rt[t[x][0]-1],yy=rt[t[x][1]];
104         //k=s[yy]-s[xx]+1-k;
105         while(l!=r)
106         {
107            int mid=(l+r)>>1,t=s[ls[yy]]-s[ls[xx]];
108            if(t>=k){xx=ls[xx];yy=ls[yy];r=mid;}
109            else {xx=rs[xx];yy=rs[yy];l=mid+1;k-=t;}
110         }
111         printf("%d
",b[l]);
112     }
113 
114     return 0;
115 
116 }

View Code