80744 - 同测活动第4场提高组完善程序2
统计题目(材料题)
给定一棵有n个节点的树，树以节点1为根。程序使用倍增算法求解树上任意两个节点的最近公共祖先(LCA)。最近公共祖先是指两个节点在树上的公共祖先中深度最大的那个节点。当有多组问询时，按照问询的顺序，依次输出每个问询的答案。
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 200009;
4
5 vector<int> to[N];
6 int L, n, q, p[N][20];
7 int tI[N], to[N], timer;
8
9 void dfs(int u, int fa) {
10 tI[u] = ++timer;
11 p[u][0] = fa;
12 for (int i = 1; i <= L; ++i) p[u][i] = ①;
13 for (int i = 0; i < to[u].size(); ++i)
14 if (to[u][i] != fa) dfs(to[u][i], u);
15 to[u] = ++timer;
16 }
17
18 bool up(int u, int v) {
19 return ②;
20 }
21
22 int lca(int u, int v) {
23 if (up(u, v)) return u;
24 if (up(v, u)) return v;
25 for (int i = L; i >= 0; --i)
26 if (③) u = p[u][i];
27 return ④;
28 }
29
30 int main() {
31 cin >> n;
32 for (int i = 1; i <= n - 1; i++) {
33 int u, v;
34 cin >> u >> v;
35 to[u].push_back(v);
36 to[v].push_back(u);
37 }
38 L = 1;
39 while (⑤) ++L;
40 dfs(1, 0);
41
42 cin >> q;
43
44 for (int i = 1; i <= q; i++) {
45 int x, y;
46 cin >> x >> y;
47 cout << lca(x, y) << endl;
48 }
49 return 0;
50 }
关注我们
