首页 > 代码库 > BZOJ1803: Spoj1487 Query on a tree III
BZOJ1803: Spoj1487 Query on a tree III
1803: Spoj1487 Query on a tree III
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 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
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\n",b[l]);112 }113 114 return 0;115 116 }
BZOJ1803: Spoj1487 Query on a tree III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。