倍增 & Tarjan 求解LCA
什么是LCA?假设我们有一棵树：
1
/ \
2 3
/ \ /
4 5 6对于 \(2\) 和 \(6\) 的LCA，就是最近公共祖先，即为距离 \(2\) 和 \(6\) 最近的两个节点公有的节点。怎么求呢？这里就有三种算法。
普通算法
我们可以把这一棵树存好，方式随便（这里展示使用邻接表），可以看到存好之后的树如下：
1 - 2 - 3
2 - 1 - 4 - 5
3 - 1 - 6
4 - 2
5 - 2
6 - 3其中 \(4,5,6\) 均为叶子节点。现在我们假设要求 \(2\) 和 \(6\) 的LCA,步骤如下：
[*]首先，因为 \(6\) 的深度 \(>2\) 所以我们要 \(6\) 先跳到 \(2\) 的高度。
[*]此时，我们的 \(6\) 节点来到了 \(3\) 节点,\(2\) 节点不变。
[*]现在，把 \(2\) 和 \(3\) 节点同时上提。
[*]经过一次上提之后，两个节点都来到了 \(1\) 位置。那么 \(1\) 就是 \(2\) 和 \(6\) 的LCA。
算法实现如下：
#include #include #include using namespace std;const int MAXN = 500010;vector tree;int depth;int parent;// DFS预处理每个节点的深度和父节点void dfs(int u, int p) { parent = p; depth = depth + 1; for (int v : tree) { if (v != p) { dfs(v, u); } }}// 暴力方法求LCAint lca(int u, int v) { // 将两个节点提到同一深度 while (depth > depth) u = parent; while (depth > depth) v = parent; // 然后一起向上找 while (u != v) { u = parent; v = parent; } return u;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, S; cin >> N >> M >> S; // 建树 for (int i = 1; i < N; ++i) { int x, y; cin >> x >> y; tree.push_back(y); tree.push_back(x); } // 预处理 depth = -1; // 根节点的父节点设为0，深度为-1+1=0 dfs(S, 0); // 处理查询 while (M--) { int a, b; cin >> a >> b; cout = depth) { u = parent; } } // 如果此时u==v，说明v就是u的祖先 if (u == v) return u; // 现在u和v在同一深度，一起向上找LCA for (int k = LOG-1; k >= 0; --k) { if (parent != parent) { u = parent; v = parent; } } // 此时u和v的父节点就是LCA return parent;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, S; cin >> N >> M >> S; // 建树 for (int i = 1; i < N; ++i) { int x, y; cin >> x >> y; tree.push_back(y); tree.push_back(x); } // 初始化 depth = -1; // 虚拟根节点的深度设为-1，这样根节点S的深度为0 // 预处理 dfs(S, 0); // 0作为虚拟父节点 // 处理查询 while (M--) { int a, b; cin >> a >> b; coutN >> M >> S; // 建树 for (int i = 1; i < N; ++i) { int x, y; cin >> x >> y; tree.push_back(y); tree.push_back(x); } // 存储查询 for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; // 双向存储查询 queries.emplace_back(b, i); if (a != b) { queries.emplace_back(a, i); } } // 运行Tarjan算法 tarjan(S); // 输出查询结果 for (int i = 0; i < M; ++i) { cout
页:
[1]