首页 > 代码库 > 【bzoj1803】Spoj1487 Query on a tree III DFS序+主席树
【bzoj1803】Spoj1487 Query on a tree III DFS序+主席树
题目描述
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.
输入
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)
输出
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.
样例输入
5 1 3 5 2 7 1 2 2 3 1 4 3 5 4 2 3 4 1 3 2 3 2
样例输出
5 4 5 5
题目大意
给出一棵以1为根的树，每个点有一个点权。多次询问每个点为根的子树中权值第k小的点是哪个
题解
DFS序+主席树
我也不知道为什么k-th largest number是第k小的意思。反正第k小既能解释样例又能A题。
维护一个DFS序，然后子树就转化为一段连续的区间，我们要求区间第k小。
直接裸上主席树即可。
#include <cstdio> #include <algorithm> #define N 100010 using namespace std; int w[N] , s[N] , r[N] , head[N] , to[N << 1] , nxt[N << 1] , cnt , pos[N] , v[N] , last[N] , tot , root[N] , ls[N * 18] , rs[N * 18] , si[N * 18] , num; void add(int x , int y) { to[++cnt] = y , nxt[cnt] = head[x] , head[x] = cnt; } void dfs(int x , int fa) { int i; pos[x] = ++tot , v[tot] = w[x]; for(i = head[x] ; i ; i = nxt[i]) if(to[i] != fa) dfs(to[i] , x); last[x] = tot; } void ins(int p , int l , int r , int x , int &y) { y = ++num , si[y] = si[x] + 1; if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) rs[y] = rs[x] , ins(p , l , mid , ls[x] , ls[y]); else ls[y] = ls[x] , ins(p , mid + 1 , r , rs[x] , rs[y]); } int query(int k , int l , int r , int x , int y) { if(l == r) return l; int mid = (l + r) >> 1; if(k <= si[ls[y]] - si[ls[x]]) return query(k , l , mid , ls[x] , ls[y]); else return query(k - si[ls[y]] + si[ls[x]] , mid + 1 , r , rs[x] , rs[y]); } int main() { int n , m , i , x , y; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , s[i] = w[i]; sort(s + 1 , s + n + 1); for(i = 1 ; i <= n ; i ++ ) w[i] = lower_bound(s + 1 , s + n + 1 , w[i]) - s , r[w[i]] = i; for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); dfs(1 , 0); for(i = 1 ; i <= n ; i ++ ) ins(v[i] , 1 , n , root[i - 1] , root[i]); scanf("%d" , &m); while(m -- ) scanf("%d%d" , &x , &y) , printf("%d\n" , r[query(y , 1 , n , root[pos[x] - 1] , root[last[x]])]); return 0; }
【bzoj1803】Spoj1487 Query on a tree III DFS序+主席树