OI

BZOJ 1803: 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1
2
3
4

5
4
5
5

 Solution

先DFS，然后建主席树即可。写这题主要是记一下可以在DFS中建主席树、sort的时候要加一（我还WA了两发。。。）、询问的时候可以不递归询问。

听Vani说，原先这种题有种专门的数据结构：划分树。感兴趣的同学可以上度娘搜索相关文章。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
typedef long long LL;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
const int MAXN = 100005;
struct edge_type {
    int to, next;
} edge[MAXN<<1];
int h[MAXN], cnte = 0;
void ins(int u, int v) {
    edge[++cnte].to = v;
    edge[cnte].next = h[u];
    h[u] = cnte;
}
int dfn[MAXN], dfs_clock = 0, w[MAXN], dfnn[MAXN];
int tot = 0, lc[MAXN*50], rc[MAXN*50], siz[MAXN*50];
int n, root[MAXN];
void change(int &x, int y, int l, int r, int val) {
    x = ++tot; siz[x] = siz[y] + 1;
    if (l == r) return;
    lc[x] = lc[y]; rc[x] = rc[y];
    int mid = (l + r) >> 1;
    if (val <= mid) change(lc[x], lc[y], l, mid, val);
    else change(rc[x], rc[y], mid + 1, r, val);
}
int id[MAXN];
void dfs(int now, int father) {
    dfn[now] = ++dfs_clock; change(root[dfs_clock], root[dfs_clock-1], 1, n, w[now]);
    for (int i = h[now]; i; i = edge[i].next) {
        if (edge[i].to == father) continue;
        dfs(edge[i].to, now);
    }
    dfnn[now] = dfs_clock;
}
bool cmpw(int x, int y) { return w[x] < w[y]; }
int main() {
	int x, y, l, r, k, xx, yy, mid, t;
    n = getint();
    for (int i = 1; i <= n; ++i) { w[i] = getint(); id[i] = i; };
    sort(id+1, id+n+1, cmpw);
    for (int i = 1; i <= n; ++i) w[id[i]] = i;
    for (int i = 1; i < n; ++i) {
        x = getint(); y = getint();
        ins(x, y); ins(y, x);
    }
    dfs(1, 0);
    int m = getint();
    while (m--) {
        x = getint(); y = getint();
		k = y;
		xx = root[dfn[x]-1];
		yy = root[dfnn[x]];
		l = 1;
		r = n;
		while (l < r) {
			mid = (l + r) >> 1;
			t = siz[lc[yy]] - siz[lc[xx]];
			if (k <= t) {
				xx = lc[xx]; yy = lc[yy]; r = mid;
			} else {
				xx = rc[xx]; yy = rc[yy]; l = mid + 1; k -= t;
			}
		}
        printf("%d\n", id[l]);
    }
    return 0;
}