树上倍增算法详解（小白也能学会的LCA求解方法）

为什么需要树上倍增？

最朴素的方法是先让两个节点跳到同一深度，再同时向上跳，直到相遇。但这种方法在最坏情况下时间复杂度为O(n)，效率太低。

树上倍增通过预处理每个节点向上跳 $2^k$ 步所能到达的祖先，使得每次查询可以在 $O(\log n)$ 时间内完成，大大提升了效率。

核心思想

我们定义一个二维数组 up[u][k] 表示节点 u 向上跳 $2^k$ 步后到达的祖先节点。

关键递推关系如下：

// up[u][0] 是 u 的直接父节点up[u][k] = up[ up[u][k-1] ][k-1];  // 跳 2^(k-1) 步后再跳 2^(k-1) 步 = 跳 2^k 步  

算法步骤

1. 预处理深度和父节点：通过DFS或BFS计算每个节点的深度和直接父节点（即 up[u][0]）。
2. 构建倍增表：利用递推公式填充 up[u][k] 数组。
3. 查询LCA：
   • 先将较深的节点上移至与另一个节点同一深度；
   • 若此时两节点相同，则返回该节点；
   • 否则，从最大可能的 $k$ 开始，若 up[a][k] != up[b][k]，则同时上移；
   • 最后返回它们的直接父节点（即 up[a][0]）。

C++完整实现

#include <iostream>#include <vector>#include <cmath>using namespace std;const int MAXN = 100005;const int LOG = 17; // 因为 2^17 > 100000vector<int> graph[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 : graph[u]) {        if (v != parent) {            dfs(v, u);        }    }}// 查询LCAint lca(int a, int b) {    if (depth[a] < depth[b]) swap(a, b);    // 将a提升到与b同一深度    int diff = depth[a] - depth[b];    for (int i = 0; i < LOG; i++) {        if (diff & (1 << i)) {            a = up[a][i];        }    }    if (a == b) return a;    // 同时向上跳    for (int i = LOG - 1; i >= 0; i--) {        if (up[a][i] != up[b][i]) {            a = up[a][i];            b = up[b][i];        }    }    return up[a][0];}int main() {    int n, q;    cin >> n >> q;    for (int i = 0; i < n - 1; i++) {        int u, v;        cin >> u >> v;        graph[u].push_back(v);        graph[v].push_back(u);    }    depth[0] = -1; // 根节点的父节点设为0，其深度为-1    dfs(1, 0);     // 假设根节点为1    while (q--) {        int a, b;        cin >> a >> b;        cout << lca(a, b) << '\n';    }    return 0;}  

时间复杂度分析

• 预处理：DFS遍历整棵树 O(n)，构建倍增表 O(n log n)
• 单次查询：O(log n)

因此，对于大量查询（如10⁵次），树上倍增比朴素方法快得多。

应用场景

除了求LCA，树上倍增还可用于：

• 求树上两点间距离
• 动态维护路径上的最大/最小值
• 在线回答树链相关问题

总结

通过本教程，你应该已经掌握了树上倍增的基本原理和实现方法。记住，关键在于理解“倍增”思想——用二进制拆分跳跃步长，从而将线性操作优化为对数级别。多练习几道题（如洛谷P3379），你就能熟练运用这一强大工具！

关键词：树上倍增, LCA算法, C++树结构, 倍增法求最近公共祖先