Description
给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。
Input
第一行两个整数N,M。 第二行有N个整数,其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y),表示点x到点y有一条边。 最后M行每行两个整数(u,v,k),表示一组询问。
Output
M行,表示每个询问的答案。
Sample Input
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2
Sample Output
2
8
9
105
7
HINT
HINT:
N,M<=100000 暴力自重。。。
Source
鸣谢seter
树上建主席树就好了呀。每次查询,先倍增求lca, 然后根据 tree[tree[x].l].cnt + tree[tree[y].l].cnt - tree[tree[z].l].cnt - tree[tree[F].l].cnt 决定往左边还是往右边走。
x y 是给定的两点 z是lca F是fa[lca]
犯了一些sb错误,比如 求jump数组的时候放到了dfs外面……
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int SZ = 1e5 + 10; struct Edge { int f, t; }es[SZ * 2]; struct SGT { int l, r, cnt; }tree[SZ * 40]; int n, m, lsh[SZ], first[SZ * 2], nxt[SZ * 2], num[SZ], tot = 1, cnt, len; int fa[SZ], jump[SZ][25], depth[SZ], rt[SZ], Tcnt; bool vis[SZ]; void read(int &num) { num = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();} while('0' <= c && c <= '9'){num = num * 10 + (c - '0'); c = getchar();} num *= f; } void build(int f, int t) { es[++tot] = (Edge){f, t}; nxt[tot] = first[f]; first[f] = tot; es[++tot] = (Edge){t, f}; nxt[tot] = first[t]; first[t] = tot; } void insert(int l, int r, int x, int &y, int v) { y = ++Tcnt; tree[y] = tree[x]; tree[y].cnt++; if(l == r) return ; int mid = (l + r) >> 1; if(v <= mid) insert(l, mid, tree[x].l, tree[y].l, v); else insert(mid + 1, r, tree[x].r, tree[y].r, v); } void dfs(int u) { insert(1, n, rt[fa[u]], rt[u], num[u]); for(int j = 1; j <= 20; j++) jump[u][j] = jump[jump[u][j - 1]][j - 1]; vis[u] = 1; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(vis[v]) continue; fa[v] = jump[v][0] = u; depth[v] = depth[u] + 1; dfs(v); } } int get_lca(int u, int v) { if(depth[u] < depth[v]) swap(u, v); int t = depth[u] - depth[v]; for(int i = 0; i <= 20; i++) if(t & (1 << i)) u = jump[u][i]; for(int i = 20; i >= 0; i--) if(jump[u][i] != jump[v][i]) u = jump[u][i], v = jump[v][i]; return u == v ? u : fa[u]; } int ask(int l, int r, int x, int y, int z, int F, int k) { if(l == r) return l; int mid = (l + r) >> 1; int tmp = tree[tree[x].l].cnt + tree[tree[y].l].cnt - tree[tree[z].l].cnt - tree[tree[F].l].cnt; if(tmp >= k) return ask(l, mid, tree[x].l, tree[y].l, tree[z].l, tree[F].l, k); else return ask(mid + 1, r, tree[x].r, tree[y].r, tree[z].r, tree[F].r, k - tmp); } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &num[i]), lsh[i] = num[i]; sort(lsh + 1, lsh + 1 + n); len = unique(lsh + 1, lsh + 1 + n) - lsh - 1; for(int i = 1; i <= n; i++) num[i] = lower_bound(lsh + 1, lsh + 1 + len, num[i]) - lsh; int u, v; for(int i = 1; i < n; i++) { scanf("%d%d", &u, &v); build(u, v); } depth[1] = 1; dfs(1); int k, lastans = 0; while(m--) { scanf("%d%d%d", &u, &v, &k); u ^= lastans; int lca = get_lca(u, v); printf("%d", lastans = lsh[ask(1, n, rt[u], rt[v], rt[lca], rt[fa[lca]], k)]); if(m) puts(""); } return 0; } |