倍增求 LCA

一句话算法

倍增 LCA 先让深的点向上跳到同一层，再让两个点一起从大步到小步向上跳。

问题模型

给定一棵有根树，需要多次查询两个点 $u$ 和 $v$ 的最近公共祖先。

树必须先选定根。根不同，祖先关系也可能不同，所以如果题目给出了根节点 $s$，预处理时就应该从 $s$ 开始 DFS；只有题目没有指定根时，才通常把 $1$ 当作根。

常见扩展查询：

• 两点距离：$\text{depth}[u] + \text{depth}[v] - 2 \times \text{depth}[\text{lca}(u, v)]$。
• 判断祖先关系。
• 树上路径拆分。
• 树上差分。

核心直觉

如果一个点比另一个点深，两个点不在同一层，就不能直接比较祖先。

第一步先把深的点往上提到同一深度。为了不一步一步跳，我们预处理：

这样任意距离都可以拆成若干个二进制位。例如要上跳 $13$ 层：

就依次跳 $2^3$、$2^2$、$2^0$。

算法步骤

预处理

任选一个根节点，一般取 $1$；如果题目给出根节点，就使用题目给出的根。

DFS 整棵树，求出：

• $\text{depth}[u]$：节点 $u$ 的深度。
• $\text{up}[u][0]$：节点 $u$ 的父亲。
• $\text{up}[u][j]$：节点 $u$ 的 $2^j$ 级祖先。
• DFS 序的进入时间和离开时间：如果需要 $O(1)$ 判断祖先关系，可以额外维护 in[u] 和 out[u]。

倍增表的层数 LOG 要满足 $2^{\text{LOG}} > n$。如果写成固定常量，需要保证它覆盖题目的最大 $n$；如果题目规模变化大，更稳妥的做法是在程序里按 $n$ 计算。

转移式：

直觉是：$2^j$ 级祖先 = 先跳 $2^{j-1}$，再从那个位置继续跳 $2^{j-1}$。

第 k 祖先

倍增表不仅能求 LCA，也能回答“节点 $u$ 的第 $k$ 级祖先是谁”。

把 $k$ 拆成二进制位，从低位到高位检查：

        
1
2
3

        for (int j = 0; j < LOG; ++j) {
    if (k & (1 << j)) u = up[u][j];
}
    

例如 $k = 13$，因为 $13 = 8 + 4 + 1$，所以依次跳 $2^3$、$2^2$、$2^0$。这个操作正是查询 LCA 时“把深点提到同一深度”的基础。

查询 LCA

查询 $\text{lca}(a, b)$：

1. 如果 $a$ 比 $b$ 浅，交换它们，保证 $a$ 更深。
2. 让 $a$ 上跳 $\text{depth}[a] - \text{depth}[b]$ 层，使两点同深。
3. 如果此时 $a = b$，说明浅点就是 LCA。
4. 从大到小枚举 $j$：
   • 如果 $\text{up}[a][j] \neq \text{up}[b][j]$，说明还没跳过 LCA，可以同时上跳。
   • 如果相同，说明这一步会跳到 LCA 或 LCA 之上，暂时不能跳。
5. 循环结束时，$a$ 和 $b$ 停在 LCA 的两个不同儿子子树中，答案是 $\text{up}[a][0]$。

祖先关系判断

判断 $u$ 是否为 $v$ 的祖先，常见有两种写法。

第一种直接用 LCA：

第二种用 DFS 序。预处理进入时间 in[u] 和离开时间 out[u] 后：

        
1
2
3

        bool is_ancestor(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
    

如果文章只需要基础 LCA，第一种足够；如果后续还要做子树判断、虚树或路径包含判断，第二种更方便。

算法证明

一、同深不丢答案

假设 $a$ 更深。

LCA 一定是 $a$ 的祖先，也是 $b$ 的祖先，所以 $a$ 到 LCA 的路径长度不少于 $b$ 到 LCA 的路径长度。先把 $a$ 上跳到和 $b$ 同深，只会删除 $a$ 到 LCA 下方的那段路径，不会跳过 LCA。

因此同深后，LCA 仍然是两个点的公共祖先。

二、从大到小同时跳是正确的

同深后，如果 $a \neq b$，它们分别在 LCA 的不同分支里。

从大到小枚举 $j$ 时：

• 如果 $\text{up}[a][j] \neq \text{up}[b][j]$，两者跳完仍在 LCA 下方的不同分支，可以安全跳。
• 如果 $\text{up}[a][j] = \text{up}[b][j]$，这次跳会把它们汇合到同一个祖先，可能已经到达或越过 LCA，所以不能跳。

循环结束后，已经不能再让两个点保持“不同祖先”地向上跳。此时它们正好在 LCA 的下面一层，所以父亲就是 LCA。

复杂度分析

设树有 $n$ 个节点。

• 预处理时间复杂度：$O(n \log n)$。
• 单次查询时间复杂度：$O(\log n)$。
• 空间复杂度：$O(n \log n)$。

如果额外维护 DFS 序，预处理时间仍是 $O(n \log n)$，空间只多出 $O(n)$。

扩展：路径信息一起倍增

很多题不只问 LCA，还会问路径上的最大边、最小边、边权和等信息。这时可以在 up[u][j] 旁边再维护一个同样大小的表。

例如维护从 $u$ 向上跳 $2^j$ 条边经过的最大边权：

它的含义和 up 表完全一样：一段长度 $2^j$ 的路径，被拆成两段长度 $2^{j-1}$ 的路径。

查询两点路径信息时，仍然先把深点提到同深，再同时上跳；每一次跳跃时，把对应的路径信息合并进答案即可。

常见扩展：

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

        #include <algorithm>
#include <vector>
#include <cstring>

const int maxn = 1e6 + 5;
using Graph = std::vector<int>;
Graph tree[maxn];  // 全局邻接表数组：直接向 tree[u] 加无权边

// 如何使用：
// 1. 读入边：tree[u].push_back(v); tree[v].push_back(u);
// 2. BinaryLCA lca(n);
// 3. lca.build(root);               // 构建/预处理 DFS 深度和倍增表（默认 root = 1）
// 4. int p = lca.query(a, b);       // 查询 a 和 b 的 LCA（或使用 lca.lca(a, b)）
// 5. int d = lca.dist(a, b);        // 查询 a 和 b 在树上的距离

// 倍增算法求最近公共祖先（LCA）与树上距离
struct BinaryLCA {
    constexpr static int maxn = 1e6 + 5;
    constexpr static int max_log = 20;  // 支持最多 2^20 = 1,048,576 个节点
    int n;
    int depth[maxn];
    int up[maxn][max_log]; // up[u][j] 表示节点 u 的 2^j 级祖先

    explicit BinaryLCA(int n = 0) : n(n) {
        memset(up, 0, sizeof(up));
        for (int i = 0; i <= n; ++i) depth[i] = 0;
    }

    // DFS 预处理每个节点的深度 depth 以及 2^j 级祖先表 up
    void dfs(int u, int fa) {
        up[u][0] = fa;
        depth[u] = depth[fa] + 1;
        for (int j = 1; j < max_log; ++j) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        for (int v : tree[u]) {
            if (v == fa) continue;
            dfs(v, u);
        }
    }

    // 构建/预处理 LCA 倍增表，默认以 root 为根节点
    void build(int root = 1) {
        depth[0] = 0;
        dfs(root, 0);
    }

    // 查询节点 u 的第 k 级祖先（向上跳 k 步）
    int kth_ancestor(int u, int k) {
        for (int j = 0; j < max_log; ++j) {
            if (k & (1 << j)) u = up[u][j];
        }
        return u;
    }

    // 查询节点 a 和节点 b 的最近公共祖先（LCA）
    int lca(int a, int b) {
        //保证 a  是较深节点
        if (depth[a] < depth[b]) std::swap(a, b);

        a = kth_ancestor(a, depth[a] - depth[b]);
        if (a == b) return a;

        for (int j = max_log - 1; j >= 0; --j) {
            if (up[a][j] != up[b][j]) {
                a = up[a][j];
                b = up[b][j];
            }
        }
        return up[a][0];
    }


    // 计算节点 a 和节点 b 在树上的距离
    int dist(int a, int b) {
        int c = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[c];
    }
};
    

测试用例

树结构：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

查询结果：

应用分类详解

LCA 的本质是把树上两点路径拆成“向上到公共祖先”的两段。

一、树上路径查询

典型模式： 题目反复询问两点路径上的长度、权值和、最大值或最小值。

识别信号： 多次询问 $u$ 到 $v$ 的路径，路径经过它们的公共祖先。

核心建模： 先找到 $\text{lca}(u, v)$，再把路径拆成 $u \to \text{lca}$ 和 $v \to \text{lca}$。

二、祖先关系判断

典型模式： 判断一个点是否在另一个点的子树里，或某个点是否位于路径上。

识别信号： 祖先、后代、子树、路径经过。

核心建模： 用 LCA 或 DFS 序判断包含关系。

三、树上差分

典型模式： 多次给树上路径加一，最后统计点或边的贡献。

识别信号： 多条路径、路径覆盖次数、最后统一统计。

核心建模： 对路径两端加贡献，在 LCA 和 LCA 的父亲处抵消，然后 DFS 汇总。

四、第 k 祖先与向上跳跃

典型模式： 询问某个点向上走 $k$ 步后到达哪里，或模拟很多次向父亲移动。

识别信号： 第 $k$ 个祖先、向上跳 $k$ 层、父亲指针、撤销到某个历史状态。

核心建模： 把 $k$ 拆成二进制，用 up[u][j] 一次跳 $2^j$ 步。

五、路径信息维护

典型模式： 多次询问树上两点路径的最大边、最小边、边权和或瓶颈值。

识别信号： 树上路径、边权最大值、瓶颈、替换一条边、次小生成树。

核心建模： LCA 负责把路径拆成两段；倍增表在跳跃时同步合并路径信息。

方法对比

LCA 有多种求法，倍增不是唯一方法，但它最适合当作竞赛里的通用模板。

如果题目只问 LCA，倍增写法已经足够稳定；如果题目还要路径加、路径和、路径最大值等复合操作，再考虑树链剖分或在倍增表里维护额外信息。

易错点

• LOG 不够大：必须保证 $2^{\text{LOG}} > n$。
• 根节点用错：题目给根时，预处理要从题目给定的根开始。
• 忘记处理祖先关系：同深后如果 $a = b$，应立即返回。
• 根的父亲处理不一致：常见做法是令根的父亲为 0 或根自己，但整份代码要统一。
• 递归 DFS 爆栈：当 $n$ 很大且树退化成链时，递归深度可能达到 $n$。
• 带权扩展多算边：路径信息只在实际上跳时合并，不要把 LCA 上方的边算进答案。

经典例题

• luogu-P3379 【模板】最近公共祖先：倍增 LCA 标准模板题。
• luogu-P3258 松鼠的新家：把连续经过的树上路径转成多次路径加，最后用树上差分统计每个点的经过次数。
• luogu-P1967 货车运输：先建最大生成树，再用 LCA 倍增维护路径最小边权，查询两点间最大载重量。
• luogu-P4180 严格次小生成树：枚举非树边，用 LCA 倍增查询树上路径最大边和严格次大边。
• luogu-P5903 树上 K 级祖先：直接练习 kth_ancestor，把 $k$ 拆成二进制位向上跳。

参考

• 本书相关章节：倍增跳跃、DFS 序、ST 表、树链剖分