首页 > 代码库 > 【BZOJ1803】Spoj1487 Query on a tree III 主席树+DFS序
【BZOJ1803】Spoj1487 Query on a tree III 主席树+DFS序
【BZOJ1803】Spoj1487 Query on a tree III
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大？（the k_th largest）分明是第k小啊！
直接主席树+DFS序搞定。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=100010; int n,m,cnt,tot; int to[maxn<<1],next[maxn<<1],head[maxn],v[maxn],p[maxn],q[maxn],rt[maxn]; int ls[maxn*30],rs[maxn*30],siz[maxn*30],s[maxn*30]; struct number { int val,org; }num[maxn]; bool cmp(number a,number b) { return a.val<b.val; } void insert(int x,int &y,int l,int r,int a,int b) { if(l>r) return ; y=++tot,siz[y]=siz[x]+1; if(l==r) { s[y]=b; return ; } int mid=l+r>>1; if(a<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,a,b); else ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,a,b); } int query(int a,int b,int l,int r,int c) { if(l==r) return s[a]; int mid=l+r>>1,sm=siz[ls[a]]-siz[ls[b]]; if(c<=sm) return query(ls[a],ls[b],l,mid,c); else return query(rs[a],rs[b],mid+1,r,c-sm); } void dfs(int x,int fa) { p[x]=++p[0]; insert(rt[p[0]-1],rt[p[0]],1,n,v[x],x); for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) dfs(to[i],x); q[x]=p[0]; } void add(int a,int b) { to[cnt]=b,next[cnt]=head[a],head[a]=cnt++; } int main() { scanf("%d",&n); int i,a,b; for(i=1;i<=n;i++) scanf("%d",&num[i].val),num[i].org=i; sort(num+1,num+n+1,cmp); for(i=1;i<=n;i++) v[num[i].org]=i; memset(head,-1,sizeof(head)); for(i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } dfs(1,0); scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); printf("%d\n",query(rt[q[a]],rt[p[a]-1],1,n,b)); } return 0; }
【BZOJ1803】Spoj1487 Query on a tree III 主席树+DFS序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。