最近公共先人模板

最近公共先人

标题：https://acm.hdu.edu.cn/showproblem.php?pid=2586

1. #include <bits/stdc++.h>
2. using u32 = unsigned;
3. using i64 = long long;
4. using u64 = unsigned long long;
5. //
6. const int N = 50010;
7. int f[N][20], d[N], dist[N];
8. int e[2*N], ne[2*N], w[2*N], h[2*N], idx;
9. int n, m, t;
10. void add(int a, int b, int c) {
11.         e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
12. }
13. std::queue<int> q;
14. void bfs() {
15.         q.push(1); // 加入根节点
16.         d[1] = 1; // 根节点的层次为1
17.         while (q.size()) {
18.                 int x = q.front();
19.                 q.pop();
20.                 for (int i = h[x]; i != -1; i = ne[i]) {
21.                         int y = e[i];
22.                         if (d[y] != -1) continue; // 当前y已经遍历到了，并且已经给深度赋值了
23.                         d[y] = d[x] + 1; // y的层次等于x的层次加一
24.                         dist[y] = dist[x] + w[i]; // y到根节点的距离为x到根节点的距离加上边(x,y)的大小
25.                         f[y][0] = x; // y向上走2的零次方步到达x
26.                         for (int j = 1; j <= t; j ++) {
27.                                 f[y][j] = f[f[y][j-1]][j-1]; // y向上走2^j步到达的点就是：y向上走2^(j-1)步到达的点，再向上走2^(j-1)步到达的点
28.                         }
29.                         q.push(y); // 加入队列
30.                 }
31.         }
32. }
34. int lca(int x, int y) {
35.         if (d[x] < d[y]) std::swap(x, y); // 使得x的层次大于y的层次
36.         for (int i = t; i >= 0; i --) {
37.                 if (d[f[x][i]] >= d[y]) {
38.                         // x向上走2^i次方步都还是比y的深度大，那么还得继续走
39.                         x = f[x][i];
40.                 }
41.         }
42.         if (x == y) return y; // 走完之后，x与y相等，那么y就是最近公共祖先，因为y的深度比较大，所以y应该是祖先
43.         // 否则的话，这两个点的深度应该是相等的
44.         for (int i = t; i >= 0; i --) {
45.                 // 同时往上移动
46.                 if (f[x][i] != f[y][i]) {
47.                         x = f[x][i];
48.                         y = f[y][i];
49.                 }
50.         }
51.         return f[x][0]; // 最终这两个点的父节点就是最近公共祖先
52. }
54. int main()
55. {
56.         int T;
57.         std::cin >> T;
58.         while (T --) {
59.                 std::cin >> n >> m;
60.                 t = (int)(log(n) / log(2)) + 1;
61.                 // 清空
62.                 memset(h, -1, sizeof h);
63.                 memset(d, -1, sizeof d);
64.                 idx = 0;
65.                 // 读入一棵树
66.                 for (int i = 1; i < n; i ++) {
67.                         int x, y, z;
68.                         std::cin >> x >> y >> z;
69.                         add(x, y, z);
70.                         add(y, x, z);
71.                 }
72.                 bfs(); // 预处理信息
73.                 // 回答问题
74.                 for (int i = 1; i <= m; i ++) {
75.                         int x, y;
76.                         std::cin >> x >> y;
77.                         std::cout << dist[x] + dist[y] - 2 * dist[lca(x, y)] << "\n"; // 两个点的距离为两个点到根节点的距离之和减去2倍最近公共祖先到根节点的距离
78.                 }
79.         }
80.         return 0;
81. }

复制代码

此时结束之后，应满足向上2^i次方步他们相称
末了x的父节点f[x][0]就是答案

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。