最近公共祖先模板
最近公共祖先题目：https://acm.hdu.edu.cn/showproblem.php?pid=2586
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
//
const int N = 50010;
int f, d, dist;
int e, ne, w, h, idx;
int n, m, t;
void add(int a, int b, int c) {
e = b, w = c, ne = h, h = idx ++;
}
std::queue<int> q;
void bfs() {
q.push(1); // 加入根节点
d = 1; // 根节点的层次为1
while (q.size()) {
int x = q.front();
q.pop();
for (int i = h; i != -1; i = ne) {
int y = e;
if (d != -1) continue; // 当前y已经遍历到了，并且已经给深度赋值了
d = d + 1; // y的层次等于x的层次加一
dist = dist + w; // y到根节点的距离为x到根节点的距离加上边(x,y)的大小
f = x; // y向上走2的零次方步到达x
for (int j = 1; j <= t; j ++) {
f = f]; // y向上走2^j步到达的点就是：y向上走2^(j-1)步到达的点，再向上走2^(j-1)步到达的点
}
q.push(y); // 加入队列
}
}
}
int lca(int x, int y) {
if (d < d) std::swap(x, y); // 使得x的层次大于y的层次
for (int i = t; i >= 0; i --) {
if (d] >= d) {
// x向上走2^i次方步都还是比y的深度大，那么还得继续走
x = f;
}
}
if (x == y) return y; // 走完之后，x与y相等，那么y就是最近公共祖先，因为y的深度比较大，所以y应该是祖先
// 否则的话，这两个点的深度应该是相等的
for (int i = t; i >= 0; i --) {
// 同时往上移动
if (f != f) {
x = f;
y = f;
}
}
return f; // 最终这两个点的父节点就是最近公共祖先
}
int main()
{
int T;
std::cin >> T;
while (T --) {
std::cin >> n >> m;
t = (int)(log(n) / log(2)) + 1;
// 清空
memset(h, -1, sizeof h);
memset(d, -1, sizeof d);
idx = 0;
// 读入一棵树
for (int i = 1; i < n; i ++) {
int x, y, z;
std::cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
bfs(); // 预处理信息
// 回答问题
for (int i = 1; i <= m; i ++) {
int x, y;
std::cin >> x >> y;
std::cout << dist + dist - 2 * dist << "\n"; // 两个点的距离为两个点到根节点的距离之和减去2倍最近公共祖先到根节点的距离
}
}
return 0;
}此时结束之后，应满足向上2^i次方步他们相等
最后x的父节点f就是答案
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]