C++算法
C++ 基础：树上 LCA（最近公共祖先）求解方法
LCA（最近公共祖先）是树结构中两个节点所有公共祖先中深度最大的节点。文章介绍了两种主要求解方法：倍增法与 Tarjan 算法。倍增法基于 DFS 预处理父节点与深度，支持在线查询，单次复杂度 O(logN)，适合动态场景；Tarjan 算法利用并查集与离线处理，时间复杂度 O(n+q)，适合静态树的大规模批量查询。文中提供了完整的 C++ 代码实现及例题解析，涵盖输入输出格式与测评数据规模说明。
LCA（最近公共祖先）是树结构中两个节点所有公共祖先中深度最大的节点。文章介绍了两种主要求解方法：倍增法与 Tarjan 算法。倍增法基于 DFS 预处理父节点与深度，支持在线查询，单次复杂度 O(logN)，适合动态场景；Tarjan 算法利用并查集与离线处理，时间复杂度 O(n+q)，适合静态树的大规模批量查询。文中提供了完整的 C++ 代码实现及例题解析，涵盖输入输出格式与测评数据规模说明。
LCA（Least Common Ancestors，最近公共祖先）是树结构中的核心概念，指两个节点所有公共祖先中距离它们最近（深度最大）的节点。
要求 LCA，应先求出每个点的深度（用 DFS）。朴素的求 LCA 方法是：不妨设 x 为深度更深的点，不断让 x 往上爬，直到 dep[x] == dep[y]。如果 x == y 就返回，如果不等于就让 x 和 y 一起往上跳，直到 x == y 再返回。思路简单，但复杂度高。因此有了倍增法求 LCA：本质上是 DP，类似 ST 表，fa[i][j] 表示 i 号节点往上走 2^j 所到的节点，当 dep[i] - 2^j >= 1 时 fa[i][j] 有效（设根节点深度为 1）。
例如：
1 | 2 | 3 | 4 \ 5
fa[5][0] = 4 (从 5 向上走 2^0)，fa[5][1] = fa[fa[5][0]][0] = 3
void dfs(int x, int p) // p:父节点 {
dep[x] = dep[p] + 1;
fa[x][0] = p;
for (int i = 1; i <= 20; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (const auto& y : g[x]) {
if (y == p) continue;
dfs(y, x);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y); // 贪心，x 向上跳，直到与 y 同层
for (int i = 20; i >= 0; i--) {
if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
}
if (x == y) return x; // 二者相同，直接返回
// 与 y 同层之后，二者同时向上跳，但要保持 x != y
for (int i = 20; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
}
return fa[x][0]; // x 的父节点就是 LCA（此时 x 和 y 的父节点相同）
}
给定一棵有 N 个节点的树，每个节点有一个唯一的编号，从 1 到 N。树的根节点是 1 号节点。接下来，你会得到 Q 个查询。对于每个查询，你将得到两个节点的编号，你的任务是找到这两个节点的最低公共祖先。
第一行包含一个整数 N，表示树的节点数。 接下来的 N-1 行，每行包含两个整数 U 和 V，表示节点 U 和节点 V 之间有一条边。 下一行包含一个整数 Q，表示查询的数量。 接下来的 Q 行，每行包含两个整数 A 和 B，表示你需要找到节点 A 和节点 B 的最低公共祖先。
对于每个查询，输出一行，该行包含一个整数，表示两个节点的最近公共祖先。
5
1 2
1 3
2 4
2 5
3
4 5
3 4
3 5
2
1
1
对于第一个查询，4 和 5 的最低公共祖先是 2。 对于第二个查询，3 和 4 的最低公共祖先是 1。 对于第三个查询，3 和 5 的最低公共祖先是 1。
2 ≤ N ≤ 10^5，1 ≤ Q ≤ 10^4，1 ≤ U,V,A,B ≤ N，题目保证输入的边形成一棵树。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 9;
int fa[N][24], dep[N];
vector<int> g[N];
void dfs(int x, int p) {
dep[x] = dep[p] + 1;
fa[x][0] = p;
for (int i = 1; i <= 20; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (const auto& y : g[x]) {
if (y == p) continue;
dfs(y, x);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
}
fa[x][];
}
{
ios::(), cin.(), cout.();
n; cin >> n;
( i = ; i < n; i++) {
u, v; cin >> u >> v;
g[u].(v), g[v].(u);
}
(, );
q; cin >> q;
(q--) {
x, y; cin >> x >> y;
cout << (x, y) << ;
}
;
}
Tarjan 算法求 LCA（基于并查集的离线算法）的核心优势在于高效处理多组查询，尤其适合需要一次性解决大量 LCA 查询的场景。
时间复杂度极低，适合大规模查询 Tarjan 算法是离线算法，其时间复杂度为 O(n + q)，其中 n 是树的节点数，q 是查询次数。对比倍增算法（在线算法，单次查询 O(logN)），当查询次数 q 很大时，Tarjan 算法的总效率更高。
利用并查集实现'路径压缩'，合并与查询高效 算法核心依赖并查集的数据结构，通过 root(x) 快速查找节点所在集合的根，并用路径压缩优化查询效率。
一次遍历处理所有查询，减少树的访问次数 算法通过深度优先搜索（DFS）遍历树一次，在回溯时完成并查集的合并，并同步处理所有与当前节点相关的查询。
适用于静态树的批量查询场景 若问题中所有查询在处理前已知（离线场景），Tarjan 算法是最优选择之一。例如批量查询树上多对节点的 LCA。
实现逻辑直观，依托 DFS 与并查集的天然契合 算法利用 DFS 的回溯特性：当遍历完一个节点的所有子树后，该节点与其子树的所有节点已被合并到同一集合，且集合的根为该节点。
Tarjan 算法求 LCA 的核心优势是离线处理下的高效性，尤其在查询数量庞大时，其 O(n + q) 的时间复杂度远优于在线算法。但需注意其局限性：必须提前知晓所有查询（无法处理动态新增的查询），且依赖并查集和 DFS 的配合。
对比而言：
#include <utility>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 2e5 + 9;
int pre[N], ans[N];
vector<int> g[N];
struct Q {
int x, id;
};
vector<Q> q[N];
int root(int x) {
return pre[x] = (pre[x] == x ? x : root(pre[x]));
}
bitset<N> vis;
void tarjan(int x, int fa) {
vis[x] = true;
for (const auto& y : g[x]) {
if (y == fa) continue;
tarjan(y, x);
pre[y] = x;
}
for (const auto& t : q[x]) {
int y = t.x, id = t.id;
if (vis[y]) ans[id] = root(y);
}
}
{
ios::(), cin.(), cout.();
n; cin >> n;
( i = ; i < n; i++) {
u, v; cin >> u >> v;
g[u].(v), g[v].(u);
}
( i = ; i <= n; i++) pre[i] = i;
m; cin >> m;
( i = ; i <= m; i++) {
x, y; cin >> x >> y;
q[x].({y, i});
q[y].({x, i});
}
(, );
( i = ; i <= m; i++) cout << ans[i] << ;
;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online