C++ LCA算法详解（从零开始掌握最近公共祖先的高效实现）

如上图所示，若我们查询节点 4 和 5 的 LCA，答案就是节点 2，因为它是它们共同祖先中深度最大的。

为什么需要高效的LCA算法？

朴素方法（比如分别记录两个节点到根的路径再找交点）的时间复杂度为 O(n)，如果要处理大量查询，效率会非常低。因此，我们需要更高效的 C++树算法来优化查询速度。

本文将介绍两种主流实现方式：

• 1. 倍增法（Binary Lifting）——支持 O(log n) 查询
• 2. Tarjan 离线算法 ——适用于批量查询

我们将重点讲解倍增法，因为它易于理解、代码简洁，且适合在线查询场景。

倍增法实现LCA（C++代码详解）

倍增法的核心思想是：预处理每个节点向上跳 2^k 步所能到达的祖先。这样在查询时，我们可以快速“跳跃”到目标深度，从而在 O(log n) 时间内完成一次 LCA 查询。

步骤概览：

1. 构建树（使用邻接表）
2. DFS 预处理深度和父节点信息
3. 构建倍增表 up[u][k]
4. 实现 LCA(u, v) 查询函数

完整C++代码实现：

#include <iostream>#include <vector>#include <cmath>using namespace std;const int MAXN = 100005;const int LOG = 17; // 因为 2^17 > 100000vector<int> adj[MAXN];int depth[MAXN];int up[MAXN][LOG];// DFS 预处理深度和直接父节点void dfs(int u, int parent) {    depth[u] = depth[parent] + 1;    up[u][0] = parent;    // 构建倍增表    for (int i = 1; i < LOG; ++i) {        up[u][i] = up[up[u][i - 1]][i - 1];    }    for (int v : adj[u]) {        if (v != parent) {            dfs(v, u);        }    }}// LCA 查询函数int lca(int u, int v) {    // 确保 u 是更深的节点    if (depth[u] < depth[v]) swap(u, v);    // 将 u 提升到与 v 同一深度    int diff = depth[u] - depth[v];    for (int i = 0; i < LOG; ++i) {        if (diff & (1 << i)) {            u = up[u][i];        }    }    // 如果此时 u == v，说明 v 是 u 的祖先    if (u == v) return u;    // 同时向上跳，直到它们的父节点相同    for (int i = LOG - 1; i >= 0; --i) {        if (up[u][i] != up[v][i]) {            u = up[u][i];            v = up[v][i];        }    }    // 返回公共祖先    return up[u][0];}int main() {    int n;    cin >> n;    // 输入 n-1 条边构建树    for (int i = 0; i < n - 1; ++i) {        int a, b;        cin >> a >> b;        adj[a].push_back(b);        adj[b].push_back(a);    }    // 以节点 1 为根进行 DFS    depth[0] = -1; // 虚拟根的深度为 -1，使根节点深度为 0    dfs(1, 0);    // 示例查询    int q;    cin >> q;    while (q--) {        int u, v;        cin >> u >> v;        cout << "LCA(" << u << ", " << v << ") = " << lca(u, v) << endl;    }    return 0;}

代码说明

• MAXN 是最大节点数，LOG 是 log₂(MAXN) 向上取整。
• up[u][k] 表示节点 u 向上跳 2ᵏ 步到达的祖先。
• DFS 中先设置直接父节点（up[u][0]），再递推更高层的祖先。
• LCA 查询分两步：先对齐深度，再同步上跳。

时间复杂度分析

• 预处理：O(n log n)
• 单次查询：O(log n)

对于大多数应用场景（如 n ≤ 10⁵，查询次数 ≤ 10⁵），这种效率完全足够。

总结

通过本教程，你已经掌握了 LCA实现教程中最实用的倍增法。无论是准备面试、参加算法竞赛，还是解决实际工程问题，这套 C++ LCA算法模板都能助你一臂之力。

记住，理解原理比死记代码更重要。建议你自己动手敲一遍代码，并尝试修改输入输出格式，加深理解。

如果你觉得这篇文章对你有帮助，欢迎分享给更多学习 C++树算法的朋友！