Codeforces 588E(倍增+归并排序合并链信息)

Codeforces 588E
题意:给一棵树$n$个点,再给$m$个人,$m$个人所在的点同时每个人都有一个编号$i$,
你的任务就是找到$uv$这条路的前$k$个人,输出其编号。

直接倍增,每个倍增记录$i$点到$2^j$个祖先的前10最小的点,然后合并信息即可。
如何合并信息呢?我们让两个数组都为有序的,用归并排序实现$O(20)$合并。

注意卡常题, 代码中标注了卡常的地方

知识点:
链合并这种思想非常方便对于查询。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}//1快读
const int MAXN = 100000 + 10, LOGS = 20;
struct myVec {
int n, a[30];//2不用vector
myVec() {n = 0, ms(a, 0);}
void ins(int x) {a[++n] = x;}
};
myVec merge(myVec &a, myVec &b) {
myVec ans;
int u = a.n, v = b.n;
int i = 1, j = 1;
while (i <= u && j <= v) {
if (a.a[i] < b.a[j]) {
ans.ins(a.a[i]), i++;
} else if (a.a[i] > b.a[j]) {
ans.ins(b.a[j]), j++;
} else ans.ins(a.a[i]), i++, j++;
}
while (i <= u) {
if (ans.a[ans.n - 1] == a.a[i]) i++;
else ans.ins(a.a[i]), i++;
}
while (j <= v) {
if (ans.a[ans.n - 1] == b.a[j]) j++;
else ans.ins(b.a[j]), j++;
}//3去重不用unique
if (ans.n > 10) ans.n = 10;
return ans;
}
int n, m, q, dep[MAXN], pre[MAXN][LOGS + 5];
vector<int> G[MAXN];
myVec c[MAXN], tax[MAXN][LOGS + 5];
inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, pre[u][0] = pa, tax[u][0] = merge(c[u], c[pa]);
for (int i = 1; i <= LOGS; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (int i = 1; i <= LOGS; i++) tax[u][i] = merge(tax[u][i - 1], tax[pre[u][i - 1]][i - 1]);
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) dfs(v, u);
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = LOGS; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i = LOGS; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void pro(int u, int v, int a) {
int lca = LCA(u, v);
myVec ans = merge(c[u], c[v]);
ans = merge(ans, c[lca]);
for (int i = LOGS; i >= 0; i--) if (dep[pre[u][i]] >= dep[lca]) ans = merge(ans, tax[u][i]), u = pre[u][i];
for (int i = LOGS; i >= 0; i--) if (dep[pre[v][i]] >= dep[lca]) ans = merge(ans, tax[v][i]), v = pre[v][i];
printf("%d ", min(a, ans.n));
for (int i = 1; i <= min(a, ans.n); i++) printf("%d ", ans.a[i]);
puts("");
}
void clean() {
dep[0] = 0;
}
int solve() {
clean();
for (int x, y, i = 1; i < n; i++) x = read(), y = read(), ins(x, y);
for (int gg, i = 1; i <= m; i++) {
gg = read();
if (c[gg].n != 10) c[gg].ins(i);
}
dfs(1, 0);
for (int i = 1; i <= q; i++) {
int v = read(), u = read(), a = read();
pro(v, u, a);
}
return 0;
}
int main() {
n = read(), m = read(), q = read(), solve();
return 0;
}
------ 本文结束 ------