最近公共祖先（LCA）与树上倍增：让家族树查询像坐电梯一样快

这是什么？用来干嘛？

在计算机科学中，树是一种常见的数据结构，就像家族谱、文件目录、比赛对阵表。给定一棵树上的两个节点，最近公共祖先（Lowest Common Ancestor, LCA） 就是它们“共同祖先”中离它们最近的那个。比如家族里，你和你的表弟的最近公共祖先是你们的爷爷，而不是曾祖父。

LCA 有很多实际应用：在社交网络中找两个人的共同好友、在游戏地图中判断两个地点是否在同一区域、在生物进化树中找两个物种最近的共同祖先……通常我们需要快速回答很多组 LCA 查询，而树上倍增（Binary Lifting）就是其中最经典的算法之一。

它的核心思想非常生活化：提前给每个节点准备一份“跳跃清单”，让它可以一次跳很多步，就像坐电梯从一楼直接到十楼，而不是一层层爬楼梯。 这样，每次查询只需要 O(log n) 的时间，预处理也只需 O(n log n)。下面我们就来一步步揭开它的秘密。

1. 生活中的例子：从爬楼梯到坐电梯

家族树中的“慢查询”

想象一棵家族树，每个节点代表一个人，边代表父子关系。现在问你：张三和李四的最近公共祖先是谁？

最笨的办法：让张三沿着父亲链一直走到根，每经过一个节点就做个标记；然后让李四也沿着父亲链往上走，遇到的第一个有标记的节点就是答案。如果张三和李四相隔很远，树很深（比如深度 100000），每次查询都要走几百上千步，非常慢。

如何“跳着走”？

有没有办法让张三和李四一次跳好多步呢？当然可以！如果我们提前知道每个人的第 2^k 级祖先（即向上走 2^k 步到达的节点），那么查询时就可以像用二进制拆分一样快速跳跃。

想象一下：你有一个“跳跃清单”，上面写着：

跳 1 步（2^0）到父亲
跳 2 步（2^1）到爷爷
跳 4 步（2^2）到曾爷爷
……

这样，只要把深度差拆成若干个 2 的幂次之和，就能在 O(log n) 步内把张三提升到和李四一样的深度。然后两人再同时跳，直到他们的下一个祖先不同，最后谁的父节点就是 LCA。

这和“坐电梯”很像：你想从 13 楼到 5 楼，电梯可以一次下 8 层、4 层、1 层，而不是每层停一次。

2. 数据结构原理：up 数组和深度

核心预备知识

我们用两个数组来存储信息：

depth[u]：节点 u 的深度，根的深度为 0（或 1，这里我们设为 0）。深度就是节点到根的距离（边数）。
up[u][k]：节点 u 的第 2^k 级祖先，即向上走 2^k 步到达的节点。特别地：
- up[u][0] 是 u 的父节点（因为 2^0 = 1 步）。
- 如果 u 的祖先不存在（比如根节点再往上），则设为 0 或 -1，这里我们用 0 作为哨兵。

递推关系：如何填写 up 表？

这个关系很好记：

up[u][k] = up[ up[u][k-1] ][k-1]

解释：从 u 向上走 2^{k-1} 步到达节点 v，再从 v 继续向上走 2^{k-1} 步，总共走了 2^{k-1} + 2^{k-1} = 2^k 步。所以 v 就是 up[u][k-1]，而 up[v][k-1] 就是 up[u][k]。

举个具体例子：假设树是

对于节点 7：父节点是 4，所以 up[7][0] = 4。
再求 up[7][1]：先走 2^0 = 1 步到 up[7][0] = 4，然后从 4 再走 2^0 = 1 步到 up[4][0] = 2，所以 up[7][1] = 2。
up[7][2]：先走 2^1 = 2 步到 up[7][1] = 2，然后从 2 再走 2^1 = 2 步到 up[2][1] = 1（因为 up[2][0]=1，up[1][0]=0，再往上就全是 0 了）。所以 up[7][2] = 1。

这样，每个节点最多需要 log₂(最大深度) 个祖先信息，通常取 LOG = 17~20 就足够处理 10^5 量级的节点。

深度差与二进制拆分

提升深度时，我们利用二进制拆分：把深度差 diff 写成二进制，比如 diff = 13，二进制为 1101，表示 8 + 4 + 1。我们就依次跳 8 步、4 步、1 步，正好对应 2^3, 2^2, 2^0。这样只需要执行 3 次跳跃，而不是 13 次。

3. 查询 LCA 的详细步骤

假设我们要查询两个节点 u 和 v 的 LCA。

第一步：深度对齐

先保证 depth[u] >= depth[v]（否则交换）。然后计算深度差 diff = depth[u] - depth[v]。

从 k=0 开始枚举，如果 diff 的二进制第 k 位是 1，就让 u = up[u][k]。这相当于一次跳 2^k 步。最终 u 和 v 的深度相等。

第二步：检查是否已经相遇

如果此时 u == v，说明 u（或 v）本身就是 LCA，直接返回。

从大到小枚举 k（从 LOG-1 到 0），如果 up[u][k] != up[v][k]，说明它们的 2^k 级祖先不同，那么它们一定还没有到达 LCA，于是让 u = up[u][k]，v = up[v][k]（一起跳上去）。经过这个循环后，u 和 v 会变成 LCA 的两个直接子节点，即它们的父亲相同。最后返回 up[u][0]（或 up[v][0]）即可。

图解：以查询 LCA(7,5) 为例

使用之前的树：

深度：1:0, 2:1, 3:1, 4:2, 5:2, 6:2, 7:3

深度对齐：depth[7]=3，depth[5]=2，diff=1。二进制 1 对应 2^0，所以 u=7 跳 1 步到 up[7][0]=4。现在 u=4，深度 2，与 v=5 深度相同。
检查是否相等：u=4，v=5，不相等。
同时向上跳：从 k=最大（假设 LOG=4，但深度最大 3，所以 k 从 1 开始足够）：
- k=1：up[4][1]=2，up[5][1]=2，两者相等，不跳。
- k=0：up[4][0]=2，up[5][0]=2，也相等，也不跳。
循环结束，返回 up[4][0]=2。所以 LCA(7,5)=2。

注意：当 up[u][k] == up[v][k] 时，我们不跳，因为如果跳了可能跳过 LCA。我们要确保在最后一步之前，u 和 v 始终在 LCA 的下方。

4. 完整代码实现（C++ 和 Python）

C++ 代码（带详细注释）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 100005;   // 最大节点数
const int LOG = 17;        // 2^17 > 100000，可调大

vector<int> adj[MAXN];     // 邻接表存树
int up[MAXN][LOG];         // up[u][k]：u的第2^k级祖先
int depth[MAXN];           // 每个节点的深度
int n;                     // 节点数

// DFS预处理：计算深度和up表
void dfs(int u, int parent) {
    up[u][0] = parent;               // 父节点
    depth[u] = depth[parent] + 1;    // 深度加1
    // 从k=1开始递推
    for (int k = 1; k < LOG; k++) {
        up[u][k] = up[ up[u][k-1] ][k-1];
    }
    // 遍历子节点
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
}

// 查询LCA
int lca(int u, int v) {
    // 确保depth[u] >= depth[v]
    if (depth[u] < depth[v]) swap(u, v);
    
    // 第一步：将u提升到与v同一深度（二进制拆分）
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++) {
        if (diff & (1 << k)) {          // 如果diff的第k位是1
            u = up[u][k];
        }
    }
    
    // 第二步：如果相遇，返回
    if (u == v) return u;
    
    // 第三步：从大到小枚举k，一起向上跳
    for (int k = LOG-1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {     // 只要祖先不同，就跳
            u = up[u][k];
            v = up[v][k];
        }
    }
    // 最后u和v的父亲就是LCA
    return up[u][0];
}

int main() {
    cout << "请输入节点数n: ";
    cin >> n;
    cout << "请输入n-1条边 (u v):" << endl;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 根节点设为1，哨兵节点0的深度设为-1，使根深度为0
    depth[0] = -1;
    dfs(1, 0);
    
    int q;
    cout << "请输入查询次数: ";
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA(" << u << "," << v << ") = " << lca(u, v) << endl;
    }
    return 0;
}

Python 代码（带详细注释）

import sys
sys.setrecursionlimit(1000000)

def dfs(u, parent, adj, up, depth, LOG):
    """
    DFS预处理，计算深度和up表
    :param u: 当前节点
    :param parent: 父节点
    :param adj: 邻接表
    :param up: 二维列表 up[u][k]
    :param depth: 深度数组
    :param LOG: 2^LOG 需要大于最大深度
    """
    up[u][0] = parent
    depth[u] = depth[parent] + 1 if parent != 0 else 0  # 根深度为0
    for k in range(1, LOG):
        up[u][k] = up[up[u][k-1]][k-1]   # 递推
    for v in adj[u]:
        if v != parent:
            dfs(v, u, adj, up, depth, LOG)

def lca(u, v, up, depth, LOG):
    """
    查询LCA
    """
    if depth[u] < depth[v]:
        u, v = v, u
    # 第一步：提升u到与v同一深度（二进制拆分）
    diff = depth[u] - depth[v]
    k = 0
    while diff:
        if diff & 1:          # 如果最低位是1
            u = up[u][k]
        diff >>= 1
        k += 1
    # 第二步：检查相遇
    if u == v:
        return u
    # 第三步：从大到小枚举k，同时跳
    for k in range(LOG-1, -1, -1):
        if up[u][k] != up[v][k]:
            u = up[u][k]
            v = up[v][k]
    # 返回父节点
    return up[u][0]

def main():
    n = int(input("请输入节点数n: "))
    adj = [[] for _ in range(n+1)]
    print("请输入n-1条边 (u v):")
    for _ in range(n-1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # LOG取节点数的二进制位数，足够大
    LOG = (n).bit_length()
    up = [[0]*LOG for _ in range(n+1)]
    depth = [0]*(n+1)
    dfs(1, 0, adj, up, depth, LOG)
    
    q = int(input("请输入查询次数: "))
    for _ in range(q):
        u, v = map(int, input().split())
        print(f"LCA({u},{v}) = {lca(u, v, up, depth, LOG)}")

if __name__ == "__main__":
    main()

5. 新手容易犯的错误

❌ 错误1：忘记设置哨兵节点

在 C++ 中，如果节点编号从 1 开始，我们用索引 0 作为哨兵。但必须将 depth[0] 设为 -1（或合理值），否则 depth[1] 可能会变成 2（因为 depth[0] 初始为 0，depth[1] = depth[0] + 1 = 1 反而正确？其实根深度应该为 0，所以需要把 depth[0] = -1，这样 depth[1]=0。如果忘记，根深度会变成 1，导致深度不一致。Python 中通过 depth[u] = depth[parent] + 1 if parent != 0 else 0 处理。

节点编号：1=爷爷，2=爸爸，3=叔叔，4=小明，5=小华，6=小丽，7=小强。

输入：

查询几次：

程序输出：

LCA(7,5) = 2
LCA(2,7) = 2
LCA(6,7) = 1

解释：

小强(7)和小华(5)的最近公共祖先是爸爸(2)。
爸爸(2)和小强(7)的 LCA 就是爸爸自己。
小丽(6)和小强(7)的 LCA 是爷爷(1)。

7. 相关指引

掌握了树上倍增求 LCA 之后，你还可以用它解决很多树上的路径问题：

树上两点间距离：dist(u,v) = depth[u] + depth[v] - 2*depth[lca]。比如在家族树中，小强和小华相差几代？depth[7]=3, depth[5]=2, depth[lca=2]=1，所以距离 = 3+2-2*1 = 3 条边。
求树上路径的最大值/最小值：可以仿照 up 表，额外存一个 max_up[u][k] 表示向上 2^k 步路径上的最大权值。
求树上第 k 级祖先：直接用二进制拆分即可，不需要 LCA。
树剖（树链剖分）：另一种更通用的解决树上路径问题的数据结构，支持修改权值。
离线 Tarjan 算法：另一种 O(n + q) 的 LCA 算法，但只能处理离线查询。

建议你从上面的完整代码开始，自己多画几棵树，手动模拟查询过程，深刻理解“二进制拆分”和“同时跳”的思想。熟练后，你就能在比赛中又快又准地写出 LCA 代码。

8. 总结要点

树上倍增是一种经典算法，用于静态树（没有节点增删）的 LCA 查询。
预处理：O(n log n)，查询：O(log n)。
核心数据结构：depth[u] 和 up[u][k]。
查询过程分三步：深度对齐、检查相遇、同步跳跃。
注意哨兵节点、LOG 大小、二进制拆分的正确写法。
学会 LCA 后，可以扩展到树上路径最值、距离、第 k 级祖先等问题。

现在，你已经掌握了在家族树中“瞬间穿梭”的能力，尽情使用吧！

最近公共祖先（LCA）与树上倍增