最小公共祖先（LCA）的在线倍增算法

题目描述

给定一棵有 \(n\) 个节点的树，然后你需要回答 \(q\) 个查询。每个查询给出两个节点 \(u\) 和 \(v\)，要求你找出它们的最小公共祖先（Lowest Common Ancestor, LCA），即距离 \(u\) 和 \(v\) 最近的公共祖先节点。

例如，在一棵树中，节点 8 和节点 9 的 LCA 是节点 1，节点 6 和节点 7 的 LCA 是节点 3。这个问题的关键在于，如何快速回答大量查询，而不是为每次查询都重新遍历整棵树。

核心挑战：

• 朴素方法：对于每次查询，分别从 \(u\) 和 \(v\) 向上走到根，记录路径，然后找第一个公共节点。最坏情况每次查询 \(O(n)\)，总复杂度 \(O(nq)\)，在 \(n, q\) 较大时（例如 \(n, q \le 10^5\)）会超时。
• 目标：将预处理和查询分离，预处理 \(O(n \log n)\)，每次查询 \(O(\log n)\)，从而高效处理大量查询。这就是“在线”倍增算法的目标。

解题过程讲解

第一步：理解问题与基本概念

1. 树的结构：我们有一棵以任意节点为根的有根树。每个节点有唯一父节点（根节点没有）。
2. 祖先定义：一个节点 \(x\) 的祖先包括它自己、它的父节点、父节点的父节点……一直到根。
3. LCA定义：给定两个节点 \(u\) 和 \(v\)，在所有既是 \(u\) 祖先又是 \(v\) 祖先的节点中，深度最大的那一个。深度定义为从根节点到该节点的路径边数。

第二步：倍增法的核心思想

倍增法（Binary Lifting）的核心思想是“以 2 的幂次为步长向上跳”。

1. 朴素跳跃的缺点：如果一次只向上走一步（父节点），那么在最坏情况下（比如 \(u\) 是叶子，\(v\) 是根），需要走 \(O(n)\) 步。
2. 倍增跳跃的优势：我们预先计算每个节点向上走 \(2^k\) 步会到达哪个祖先。有了这个信息，我们就可以“大踏步”向上跳，快速逼近目标位置。因为任何数字都可以用二进制表示，所以从任意位置跳到任意祖先位置所需的步数，可以分解为若干个 \(2^k\) 步的和，从而在 \(O(\log n)\) 步内完成。

关键数据结构：

• depth[x]：节点 \(x\) 的深度（根的深度为 0 或 1，通常设为 0 方便计算）。
• up[x][k]：节点 \(x\) 向上走 \(2^k\) 步后到达的祖先节点。如果这一步会超出根节点，则值设为 0（假设节点编号从 1 开始，0 表示空节点）。

第三步：算法步骤详解

步骤 1：预处理——DFS 计算深度和直接父节点

首先进行一次深度优先搜索（DFS），从根节点（假设为 1）开始，计算出每个节点的 depth 和 up[x][0]（即其直接父节点）。

• 根节点的父节点设为 0。
• 对于边 (u, v)，如果 v 是 u 的子节点，则 depth[v] = depth[u] + 1，up[v][0] = u。

示例树 (1为根)：
        1
       / \
      2   3
     / \   \
    4   5   6
       / \
      7   8
查询例子: LCA(7, 8) = 5, LCA(7, 6) = 1

DFS后得到：
节点: 1 2 3 4 5 6 7 8
depth: 0 1 1 2 2 2 3 3
父节点(up[][0]): 0 1 1 2 2 3 5 5

步骤 2：预处理——倍增表（Binary Lifting Table）的构建

我们已经有 up[x][0]（向上 1 步）。如何计算 up[x][k]（向上 \(2^k\) 步）？
利用动态规划的思想：向上走 \(2^k\) 步，等于先向上走 \(2^{k-1}\) 步，然后再向上走 \(2^{k-1}\) 步。

递推公式：
up[x][k] = up[ up[x][k-1] ][k-1], 对于 \(k = 1, 2, ...\) 直到 \(\lfloor \log_2 n \rfloor\)。

解释：从 \(x\) 向上走 \(2^k\) 步，等价于从 \(x\) 向上走 \(2^{k-1}\) 步到达节点 mid = up[x][k-1]，然后再从这个 mid 节点向上走 \(2^{k-1}\) 步。

我们需要对每个节点 \(x\) 和每个 \(k\) 进行计算。通常 \(k\) 最大为 \(\lfloor \log_2 n \rfloor\)，因为树高最多为 \(n\)，\(2^k > n\) 后必然超出根。

继续示例，计算 up[7][k]：
up[7][0] = 5 (父节点)
up[7][1] = up[ up[7][0] ][0] = up[5][0] = 2 (向上2步)
up[7][2] = up[ up[7][1] ][1] = up[2][1] = up[ up[2][0] ][0] = up[1][0] = 0 (向上4步，已超出根)

对所有节点进行类似计算，完成 up 表的构建。预处理总时间复杂度为 \(O(n \log n)\)。

步骤 3：查询 LCA(u, v) 的过程

查询分为三个子步骤，目标是让 \(u\) 和 \(v\) 最终到达它们的 LCA 的下一层（即 LCA 的两个不同子节点），然后返回它们的父节点。

子步骤 3.1：将深度较大的节点向上移动，使 u 和 v 处于同一深度

假设 depth[u] > depth[v]，我们需要将 \(u\) 向上移动 delta = depth[u] - depth[v] 步，使二者深度相等。

关键技巧：将 delta 表示为二进制。例如 delta = 5 (二进制 101)，意味着我们需要向上移动 \(2^2\) 步和 \(2^0\) 步。

• 我们从最大的 \(k\) 开始尝试（比如 \(k = \lfloor \log_2 n \rfloor\) 向下）。
• 如果 depth[u] - depth[v] >= 2^k，说明这一步是“安全”的，可以跳跃，然后令 u = up[u][k]，并更新剩余的步数。
• 不断减小 \(k\)，直到 \(k=0\)，最终 depth[u] 就会等于 depth[v]。

例子：查询 LCA(7, 3)
初始：u=7 (depth=3), v=3 (depth=1)
delta = 3-1=2 (二进制 10)
k=1: 2^1=2 <= delta? 是。u = up[7][1] = 2。此时 depth[u]=2, depth[v]=1, delta=1。
k=0: 2^0=1 <= delta? 是。u = up[2][0] = 1。此时 depth[u]=1, depth[v]=1。深度已对齐。
现在 u=1, v=3，深度相同。

子步骤 3.2：如果此时 u == v，则 LCA 就是 u（或 v）

如果深度对齐后，两个节点相同，说明其中一个节点就是另一个节点的祖先，那么它就是 LCA。

例子：查询 LCA(5, 8)
对齐深度后，u=5, v=8，两者不相等。继续下一步。

子步骤 3.3：同步向上跳跃，找到 LCA 的正下方

现在 depth[u] == depth[v] 且 u != v。我们的目标是让 \(u\) 和 \(v\) 跳到它们 LCA 的两个直接子节点上。

策略：从最大的 \(k\) 开始尝试向上跳 \(2^k\) 步。

• 如果 up[u][k] != up[v][k]，说明这个跳跃不会“跳过”LCA（即跳跃后它们还没相遇），那么我们就放心地让 u = up[u][k] 和 v = up[v][k]。
• 如果 up[u][k] == up[v][k]，说明这一步跳跃可能会直接跳到 LCA 甚至更上方，我们暂时不跳，减小 \(k\) 再尝试。

这个过程的最终结果是：\(u\) 和 \(v\) 会停留在 LCA 的两个直接子节点上。那么 LCA 就是 up[u][0]（或 up[v][0]，两者相等）。

例子：查询 LCA(7, 8) （接步骤3.1对齐深度后的场景）
初始对齐深度后：u=7, v=8, depth都为3。
k 从大到小尝试 (假设最大k=2)：
k=2: up[7][2]=0, up[8][2]=0。相等(都为0)，不跳。
k=1: up[7][1]=2, up[8][1]=2。相等(都为2)，不跳。
k=0: up[7][0]=5, up[8][0]=5。相等(都为5)，不跳？等等，这里规则是“如果不相等才跳”。此时相等，所以不执行跳跃。
循环结束。此时 u=7, v=8。
LCA = up[u][0] = 5。 正确。

例子：查询 LCA(7, 6)
初始：u=7(depth3), v=6(depth2)。对齐深度。
delta=1。u = up[7][0] = 5。现在 u=5(depth2), v=6(depth2)。
k从大到小尝试：
k=1: up[5][1]=2, up[6][1]=0。不相等。所以跳！u=2, v=0? 注意，v=6, up[6][1]=0。所以跳完后 u=2, v=0。但v变成0（空节点）是允许的，我们只关心u和v不相等。
k=0: up[2][0]=1, up[0][0]=0。不相等。所以跳！u=1, v=0。
循环结束。此时 u=1, v=0。
LCA = up[u][0] = up[1][0] = 0？这里需要注意边界。当v变为0时，说明u已经跳到了LCA（根节点1）的位置。实际上，在k=0尝试时，up[2][0] 和 up[0][0] 不相等，我们执行跳跃，u变成了1。此时循环结束，u=1。LCA就是u本身，即1。算法实现中，最后返回 up[u][0] 可能会得到0。更稳健的做法是，在同步跳跃结束后，返回 up[u][0] 作为答案，但需要考虑边界。常见的写法是，在循环结束后，LCA 就是 up[u][0]（此时u和v的父亲节点就是LCA）。让我们重新审视：
在 u=5, v=6 时：
k=1: up[5][1]=2, up[6][1]=3? 等等，纠正：up[6][0]=3, up[6][1]=up[3][0]=1。所以 up[5][1]=2, up[6][1]=1。不相等，所以跳。u=2, v=1。
k=0: up[2][0]=1, up[1][0]=0。不相等，所以跳。u=1, v=0。
结束。此时 LCA 应为 up[u][0] = up[1][0] = 0？这显然不对。问题出在哪里？
关键在于，在最后一步 k=0 时，我们检查的是 up[u][k] 和 up[v][k]。如果它们不相等，我们就跳。但跳完后，u 和 v 可能位于 LCA 的下方，也可能直接变成了 LCA 和另一个无关节点。正确的逻辑应该是：我们让 u 和 v 跳到 LCA 的**正下方**。所以循环结束后，u 和 v 的父亲（即 up[u][0]）就是 LCA。
在上面的错误推演中，当 u=2, v=1 时：
k=0: up[2][0]=1, up[1][0]=0，不相等，所以我们跳，u=1, v=0。结束。此时 up[u][0]=0 不是答案。但如果我们不跳最后这一步呢？
让我们严格按照算法描述来：只有当 up[u][k] != up[v][k] 时才跳。在 u=2, v=1, k=0 时，确实 up[2][0]=1, up[1][0]=0，两者不相等，所以应该跳。跳完后 u=1, v=0。然后循环结束。此时 LCA 应该是 u 本身（因为 v 是空节点，u 是 v 的祖先）。所以最终的答案应该是 u 吗？不，算法通常的写法是返回 up[u][0]。但这里 up[1][0]=0，不对。
因此，更标准的做法是：在同步跳跃完成后，此时 u 和 v 是 LCA 的两个直接子节点（或者其中一个就是 LCA 本身，如果它们是祖先关系）。那么 LCA 一定是 up[u][0]（它也等于 up[v][0]）。但在这个例子中，最后 u=1, v=0，up[u][0]=0 不对。所以我们需要保证在跳跃过程中，v 不能变成 0（空节点）。实际上，当 v=0 时，意味着 v 已经是根节点以上的“空”祖先，这种情况发生在 u 和 v 深度对齐后，v 本身就是 u 的祖先。所以我们应当在深度对齐后，先检查是否 u == v，如果是，则直接返回 u。这已经包含在步骤3.2了。所以问题出在我的推演忽略了步骤3.2。
让我们重新正确推演 LCA(7,6)：
1. 对齐深度：u=7(d3), v=6(d2), delta=1。u = up[7][0] = 5。现在 u=5(d2), v=6(d2)。
2. 检查 u==v？ 5 != 6，继续。
3. 同步跳跃 (k从大到小，假设最大k=1)：
   k=1: up[5][1]=2, up[6][1]=1。不相等，跳。u=2, v=1。
   k=0: up[2][0]=1, up[1][0]=0。不相等，跳。u=1, v=0。
结束。此时，u=1, v=0。但我们不能直接返回 up[u][0]，因为 v 是 0。正确的逻辑是，在同步跳跃的循环中，我们只在不相等时跳，但**不检查跳完后是否会导致节点为0**。循环结束后，u 和 v 的父节点（up[u][0]）就是 LCA。这里 up[1][0]=0 显然不对。实际上，在循环结束后，u 和 v 应该分别位于 LCA 的两个子节点位置。但在 v=0 的情况下，这意味着在某个时刻，v 已经是 LCA 了（节点1），而 u 还在 LCA 的下方（节点2）。但我们在对齐深度后，两者深度相同，如果 v 是 LCA（深度1），u 的深度应该也是1，这矛盾吗？不矛盾，因为在我们对齐深度后，u=5(d2), v=6(d2)。v 并不是 LCA（LCA是1，深度0）。所以我的推演还是有误。
让我用正确的 up 表重新计算：
预处理 up 表 (k最大到1，因为树高3，2^1=2<3)：
up[1][0]=0, up[1][1]=0
up[2][0]=1, up[2][1]=0
up[3][0]=1, up[3][1]=0
up[4][0]=2, up[4][1]=0
up[5][0]=2, up[5][1]=0? 计算 up[5][1] = up[ up[5][0] ][0] = up[2][0] = 1。所以 up[5][1]=1。
up[6][0]=3, up[6][1] = up[ up[6][0] ][0] = up[3][0] = 1。
up[7][0]=5, up[7][1] = up[5][0] = 2? 等等，up[7][1] = up[ up[7][0] ][0] = up[5][0] = 2。
up[8][0]=5, up[8][1] = up[5][0] = 2。

现在查询 LCA(7,6)：
1. 对齐深度：u=7(d3), v=6(d2), delta=1。u = up[7][0] = 5。现在 u=5(d2), v=6(d2)。
2. 检查 u==v？否。
3. 同步跳跃，k从1开始：
   k=1: up[5][1]=1, up[6][1]=1。相等！所以不跳。
   k=0: up[5][0]=2, up[6][0]=3。不相等，跳。u=2, v=3。
循环结束。
LCA = up[u][0] = up[2][0] = 1。正确。

第四步：算法总结与复杂度分析

预处理：

1. DFS 计算 depth 和 up[x][0]（父节点）：\(O(n)\)。
2. 计算倍增表 up[x][k]，对于每个节点 \(x\) 和 \(k\) 从 1 到 LOG：\(O(n \log n)\)。

每次查询：

1. 对齐深度：\(O(\log n)\)。
2. 同步跳跃：\(O(\log n)\)。
   总查询复杂度：\(O(q \log n)\)。

总复杂度：\(O((n + q) \log n)\)，非常适合处理 \(n, q\) 高达 \(10^5\) 甚至 \(10^6\) 的情况。

第五步：伪代码实现

int n, l; // l = ceil(log2(n))
vector<int> adj[MAXN]; // 邻接表
int timer;
int depth[MAXN], up[MAXN][LOG];

void dfs(int v, int p) { // v: 当前节点, p: 父节点
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1]; // 注意：当 up[v][i-1] 为 0 时，up[v][i] 也会是 0
    for (int u : adj[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);
    // 对齐深度
    int diff = depth[u] - depth[v];
    for (int i = 0; (1 << i) <= diff; ++i) {
        if (diff & (1 << i)) { // 如果 diff 的二进制表示中第 i 位为 1
            u = up[u][i];
        }
    }
    if (u == v)
        return u;
    // 同步向上跳
    for (int i = l; i >= 0; --i) {
        if (up[u][i] != up[v][i]) { // 只要祖先不同就跳
            u = up[u][i];
            v = up[v][i];
        }
    }
    // 此时 u 和 v 是 LCA 的两个直接子节点
    return up[u][0];
}

// 初始化
depth[1] = 0;
l = ceil(log2(n));
dfs(1, 0);
// 然后回答查询
while (q--) {
    int u, v;
    cin >> u >> v;
    cout << lca(u, v) << endl;
}

第六步：示例运行

以之前的小树为例，查询 LCA(7, 8)：

1. 对齐深度：depth[7]=3, depth[8]=3，已对齐。
2. u != v。
3. 同步跳跃，k=1: up[7][1]=2, up[8][1]=2，相等，不跳。
   k=0: up[7][0]=5, up[8][0]=5，相等，不跳。
4. 返回 up[7][0] = 5。正确。

总结：倍增 LCA 算法通过预处理每个节点向上 \(2^k\) 步的祖先，将每次查询的复杂度从 \(O(n)\) 降为 \(O(\log n)\)，是解决树上次数众多 LCA 查询的高效方法。其核心在于利用二进制思想，将线性跳跃转化为对数步跳跃。