大树里的“家谱”：用倍增法快速找到最近公共祖先

你是不是在家族聚会时，遇到过一个难题：小明和小红都说是你的亲戚，但你知道他们俩之间是什么关系？他们共同的祖先是谁？如果把家族成员都画成一棵大树（根是最早的祖先），那么“最近公共祖先”（Lowest Common Ancestor, LCA）就是两个节点在这棵树上离它们最近的那个共同祖先。比如，小明的爸爸和小红的爸爸是兄弟，那么小明的爷爷就是他俩的最近公共祖先。

在编程中，树结构很常见：文件目录、网页导航、比赛中的队伍关系……当树很大时（比如10万个节点），用笨办法一层层往上找祖先可能会非常慢。倍增法是一种高效的技巧，它能利用“跳跃”的方式，在O(logN)时间内找到任意两个节点的最近公共祖先。下面我们一步步拆解它。

什么是最近公共祖先？用家族树举例

假设我们有一棵这样的家族树：

        0 (曾祖父)
       / \
      1   2 (爷爷)
     / \  / \
    3  4 5  6 (爸爸们)

节点编号从0开始，0是根（曾祖父），1和2是他的孩子（爷爷），3、4是1的孩子（爸爸），5、6是2的孩子。那么：

• 节点3和节点4的最近公共祖先是1（他们的爸爸）。
• 节点3和节点5的最近公共祖先是0（曾祖父）。
• 节点4和节点6的最近公共祖先是0。

传统方法为什么慢？

最直接的方法是：先让深度大的节点往上走，直到和另一个节点深度相同，然后两个节点同时一步步往上走，直到相遇。在最坏情况下（比如这棵树是一条直线，深度为N），需要走N步，对于10万个节点可能超时。

倍增法的核心思想：用“跳跃表”加速

倍增法借鉴了“二进制拆分”的思想。就像你有一张地图，上面标好了每个位置往上跳1步、2步、4步、8步…… 会到达哪个祖先。这样，无论你想往上跳多少步，都可以通过组合这些“跳跃步长”快速到达，而不用一步一步走。

例如，你想从节点u往上跳13步（13 = 8+4+1），你只需要依次跳8步、4步、1步即可——总共3步，而不是13步。

预处理：构建祖先跳跃表

我们需要两个数组：

• dep[i]：节点i的深度（根深度为0，每往下一层深度+1）。
• up[i][k]：从节点i向上跳2^k步到达的祖先节点。特别地，up[i][0]就是i的父节点。

计算up[i][k]的递推公式（想象一下“先跳一半，再跳一半”）：

up[i][k] = up[ up[i][k-1] ][k-1]

意思是：从i跳2^k步 = 先从i跳2^(k-1)步到达节点mid，再从mid跳2^(k-1)步。

预处理过程：通过深度优先搜索（DFS）遍历树，先计算父节点和深度，再计算所有up值。为了避免栈溢出，可以用递归或显式栈。

查询LCA的详细过程

假设要查询节点u和v的LCA：

第一步：让较深的节点跳到和较浅节点同一深度

• 先比较dep[u]和dep[v]，如果dep[u] < dep[v]，交换u和v，保证u更深。
• 计算深度差diff = dep[u] - dep[v]。
• 将diff拆成二进制，比如diff=13（二进制1101），那么从u依次跳1步、4步、8步（注意从低位到高位）。代码中通过循环检查diff的每一位来实现。

第二步：两个节点一起向上跳，但不跳到公共祖先

• 如果此时u和v已经相等（即u本身就是v的祖先），直接返回u。
• 否则，我们从可能的最大步长（比如LOG-1）开始，尝试让u和v同时往上跳2^k步。关键判断：如果up[u][k] != up[v][k]，说明跳完后它们还没相遇，可以安全地跳上去；如果up[u][k] == up[v][k]，说明跳过头了（到达了公共祖先或以上），此时不能跳，应该尝试更小的步长。
• 循环结束后，u和v的父节点（up[u][0]或up[v][0]）就是它们的最近公共祖先。

完整代码实现（含详细注释）

下面的代码演示了一个简单的7节点树，并查询了几个LCA。变量都用了简短英文单词，每行定义都加了中文注释。

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

const int MAXN = 100005;      // 最大节点数
const int LOG = 18;           // 因为2^17=131072，足够覆盖10万节点（LOG取17或18即可）
vector<int> g[MAXN];         // 邻接表，g[i]存放节点i的所有邻居
int up[MAXN][LOG];           // up[i][k]：从节点i向上跳2^k步的祖先
int dep[MAXN];               // 每个节点的深度（根深度为0）

// 深度优先遍历，计算每个节点的深度和祖先表
// u：当前节点，p：父节点
void dfs(int u, int p) {
    up[u][0] = p;            // 向上跳1步（2^0）就是父节点
    dep[u] = dep[p] + 1;     // 深度 = 父节点深度 + 1
    // 递推计算 up[u][1], up[u][2], ...
    for (int k = 1; k < LOG; ++k) {
        up[u][k] = up[up[u][k-1]][k-1];
    }
    // 遍历所有邻居（子节点）
    for (int v : g[u]) {
        if (v != p) {        // 避免回到父节点
            dfs(v, u);
        }
    }
}

// 查询节点u和v的最近公共祖先
int lca(int u, int v) {
    // 保证u的深度 >= v的深度
    if (dep[u] < dep[v]) swap(u, v);

    // 第一步：将u提升到与v同一深度
    int diff = dep[u] - dep[v];   // 需要往上跳的步数
    for (int k = 0; diff; ++k) {  // 从低位到高位遍历diff的二进制位
        if (diff & 1) {           // 如果当前位为1，就跳2^k步
            u = up[u][k];
        }
        diff >>= 1;               // 准备检查下一位
    }

    // 如果此时u与v相等，则u就是LCA
    if (u == v) return u;

    // 第二步：两个节点一起向上跳，尽可能接近但不等
    // 从最大的步长开始尝试
    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() {
    int N = 7;  // 节点数，下面手动构建一棵简单的树
    // 0为根，子节点1和2；1的子节点3和4；2的子节点5和6
    g[0].push_back(1); g[1].push_back(0);
    g[0].push_back(2); g[2].push_back(0);
    g[1].push_back(3); g[3].push_back(1);
    g[1].push_back(4); g[4].push_back(1);
    g[2].push_back(5); g[5].push_back(2);
    g[2].push_back(6); g[6].push_back(2);

    // 根节点0的父节点设为0（自己），深度为0
    dep[0] = 0;
    dfs(0, 0);

    // 测试几个查询
    cout << "节点3和节点4的LCA：" << lca(3,4) << endl;  // 应输出1
    cout << "节点3和节点5的LCA：" << lca(3,5) << endl;  // 应输出0
    cout << "节点4和节点6的LCA：" << lca(4,6) << endl;  // 应输出0

    return 0;
}

新手容易犯的错误

1. LOG大小不够：LOG必须满足2^(LOG-1) >= 树的最大深度。如果树有10万层，LOG至少取17（因为2^17=131072）。但注意数组up的第二维大小是LOG，如果取18就够用了。建议取20（覆盖100万节点）更安全。

2. 忘记初始化根节点的父节点和深度：上面代码中，我们手动设置了dep[0]=0，然后在dfs(0,0)中将根节点的父节点设为0（自己）。这是安全的，因为根节点往上跳不会用到。但有些实现会让父节点设为-1，此时在后续计算up时要判越界。建议统一设为根自身，简单。

3. 图是双向边但只存储单向：邻接表必须同时存储双向边，否则遍历时可能找不到子节点。注意代码中g[0].push_back(1); g[1].push_back(0);这样成对添加。

4. 递归深度过大导致栈溢出：当树很大（比如10万层）时，递归DFS可能会爆栈。解决方法是改用迭代的栈，或者设置编译器栈大小（如#pragma comment(linker, "/STACK:1024000000,1024000000")在Windows下）。不过对于一般题目，10万节点层次较浅时递归通常没问题。

5. 查询时忘记第一步的二进制拆分：有些新手直接用一个循环让u往上跳到和v同深度，比如while(dep[u] > dep[v]) u = up[u][0];，这样会退化为O(depth)。必须用二进制拆分。

6. 第二步循环中判断条件用错：正确条件是if (up[u][k] != up[v][k])，表示跳完后还没相遇，可以跳。如果写成了if (up[u][k] == up[v][k])，就会跳过头导致错误答案。

进阶思考与相关指引

• 树上求两点距离：LCA + 深度可以轻松算出两点距离：dist(u,v) = dep[u] + dep[v] - 2*dep[lca]。
• 倍增法的其他应用：除了求LCA，倍增法还可以用于快速幂、RMQ问题（但通常用ST表）、树上的路径权值和查询（配合前缀和）等。
• 替代方案：求LCA还有Tarjan离线算法（线性复杂度）、树链剖分（O(logN)但常数小），但倍增法实现简单、易理解，是最常见的在线查询方法。

掌握了倍增法，你就拥有了一把在树结构中快速“跳跃”的钥匙。试试自己构建一个更大的树，用这段代码验证几个查询吧！