树上倍增算法详解（从零开始掌握LCA与最近公共祖先的高效求解）

为什么需要树上倍增算法？

最朴素的方法是：对每个查询，先将两个节点提到同一深度，然后同时向上跳，直到它们相同。但这种方法在最坏情况下时间复杂度为O(n)，当有大量查询时效率极低。

而树上倍增算法通过预处理，可以在O(log n)的时间内回答每个LCA查询，非常适合处理大规模数据或算法竞赛中的高频查询场景。

核心思想：二进制跳跃

“倍增”指的是每次跳跃的距离是2的幂次（1, 2, 4, 8...）。我们预处理出每个节点向上跳2^k步所到达的祖先，记作 up[u][k]。

例如：
- up[u][0] 是 u 的直接父节点
- up[u][1] 是 u 的祖父节点（跳2步）
- up[u][2] 是 u 向上跳4步的祖先

状态转移方程为：
up[u][k] = up[ up[u][k-1] ][k-1]

实现步骤详解

1. 使用DFS或BFS计算每个节点的深度和直接父节点（即 up[u][0]）
2. 预处理所有 up[u][k]（k 从1到log₂n）
3. 对于每次查询 (u, v)，先调整深度，再同步向上跳

C语言完整代码实现

以下是用C语言实现的树上倍增LCA算法，包含详细注释：

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define MAXN 100005#define LOGN 17  // 因为 2^17 > 100000// 邻接表存储树int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt = 0;// 倍增表和深度数组int up[MAXN][LOGN];int depth[MAXN];// 添加边void add_edge(int u, int v) {    to[edge_cnt] = v;    nxt[edge_cnt] = head[u];    head[u] = edge_cnt++;}// DFS预处理深度和父节点void dfs(int u, int parent) {    depth[u] = (parent == -1) ? 0 : depth[parent] + 1;    up[u][0] = parent;    for (int i = 1; i < LOGN; i++) {        if (up[u][i-1] != -1) {            up[u][i] = up[ up[u][i-1] ][i-1];        } else {            up[u][i] = -1;        }    }    for (int i = head[u]; i != -1; i = nxt[i]) {        int v = to[i];        if (v != parent) {            dfs(v, u);        }    }}// 查询LCAint lca(int u, int v) {    // 确保u是更深的节点    if (depth[u] < depth[v]) {        int temp = u;        u = v;        v = temp;    }    // 将u提升到与v同一深度    int diff = depth[u] - depth[v];    for (int i = 0; i < LOGN; i++) {        if (diff & (1 << i)) {            u = up[u][i];        }    }    if (u == v) return u;    // 同时向上跳    for (int i = LOGN - 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() {    // 初始化    memset(head, -1, sizeof(head));    memset(up, -1, sizeof(up));    int n, q;    scanf("%d %d", &n, &q);    // 读入树（n-1条边）    for (int i = 0; i < n - 1; i++) {        int u, v;        scanf("%d %d", &u, &v);        add_edge(u, v);        add_edge(v, u);    }    // 从节点1开始DFS（假设根为1）    dfs(1, -1);    // 处理查询    while (q--) {        int u, v;        scanf("%d %d", &u, &v);        printf("%d\n", lca(u, v));    }    return 0;}

时间复杂度分析

• 预处理：O(n log n)
• 单次查询：O(log n)
• 总复杂度：O(n log n + q log n)，其中 q 是查询次数

应用场景

树上倍增算法不仅用于求LCA，还可扩展用于：

• 求树上两点间距离（结合深度信息）
• 动态维护路径上的最大/最小值（需额外维护信息）
• 在线算法竞赛中的高频查询问题

总结

通过本教程，你应该已经掌握了树上倍增算法的基本原理和实现方法。这项技术是解决最近公共祖先问题的利器，也是提升C++ LCA实现效率的关键。在算法竞赛中，熟练运用此类算法竞赛技巧能让你在面对复杂树形结构问题时游刃有余。

建议你动手编写代码、调试样例，加深理解。祝你在算法学习之路上越走越远！