最近公共祖先（LCA）：树上最亲近的“共同长辈”

什么是最近公共祖先？

在一棵树（比如家族树、文件夹目录树、计算机里的目录结构）上，两个节点可能有很多公共祖先。离这两个节点“最近”的那一个公共祖先，就叫最近公共祖先（Lowest Common Ancestor，简称 LCA）。

举个例子：在一个家族里，你和你表弟的公共祖先有外公外婆、曾祖父母等。其中，外公外婆是离你们最近的那一代，所以你们的最近公共祖先就是外公外婆（或爷爷奶奶，取决于血缘关系）。在计算机科学中，LCA 经常用来快速计算树上两点之间的距离、判断路径是否包含某个点、或者处理与树结构相关的问题。

为什么要学 LCA？

在树结构上，如果我们想知道两个节点之间的距离，或者找到树上的某条路径，LCA 能帮我们“抄近路”。比如：

计算树上两个节点之间的路径长度：distance(u, v) = depth[u] + depth[v] - 2 * depth[lca]
判断一个节点是否在另一个节点的子树中：lca(u, v) == u 就说明 u 是 v 的祖先
处理树上的动态规划、树上差分等问题时也经常用到 LCA

如何快速找到 LCA？—— 倍增法

有很多方法可以求 LCA，比如：

暴力法：两个节点不断向上跳到根，比较路径（太慢）
倍增法（Binary Lifting）：预处理每个节点的第 2^k 级祖先，然后像“二进制分解”一样快速上跳（常用、高效）
树链剖分：将树剖分成若干条链，利用链的顶端信息跳（稍复杂，但也很实用）

下面我们重点讲解倍增法，因为它思路清晰、代码简单，是 CSP-S 考试中的常客。

核心思想

倍增法的核心是“预处理+二进制跳跃”：

用 DFS 计算每个节点的深度（root 深度为 0）。
预处理数组 up[u][k] 表示节点 u 的第 2^k 级祖先（即向上跳 2^k 步到达的节点）。
当查询两个节点 u 和 v 的 LCA 时：
- 先把较深的节点往上跳到和较浅节点同一深度（用二进制分解深度差）。
- 然后两个节点一起向上跳，从最大的 2^k 步开始尝试，如果跳上去后两个祖先不同，就一起跳上去。最后跳不动时，它们的父节点就是 LCA。

这个方法就像你拿着家谱，先让两个人站到同一辈分，然后一起往上找共同的祖先。每次迈步子都能跳一大步（2 的幂次），所以很快。

详细步骤（配合代码理解）

假设树有根（根节点为 0 或 1），我们先用 DFS 把所有节点的深度和祖先信息算好。下面是完整代码，每一行都加了中文注释：

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

const int MAXN = 1000;      // 最大节点数
const int LOG = 10;         // 2^10 = 1024 > MAXN，够用

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

// DFS 遍历树，同时计算深度和祖先表
void dfs(int u, int p) {
    up[u][0] = p;               // 第1级祖先（父节点），根节点父节点设为-1
    for (int k = 1; k < LOG; ++k) {
        if (up[u][k-1] != -1)
            up[u][k] = up[ up[u][k-1] ][k-1];  // 2^k = 2^(k-1) + 2^(k-1)
        else
            up[u][k] = -1;       // 如果祖先不存在，设为-1
    }
    // 遍历所有子节点（排除父节点 p）
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

// 返回节点 u 和 v 的最近公共祖先
int lca(int u, int v) {
    // 先保证 u 是较深的节点
    if (depth[u] < depth[v]) swap(u, v);

    // 步骤1：把 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];
        }
    }
    // 如果此时 u 和 v 相同，直接返回
    if (u == v) return u;

    // 步骤2：两个节点一起向上跳，直到它们的父节点相同
    for (int k = LOG-1; k >= 0; --k) {
        if (up[u][k] != up[v][k]) {     // 如果跳2^k步后祖先不同，说明还没到LCA
            u = up[u][k];
            v = up[v][k];
        }
    }
    // 此时 u 和 v 的父节点就是 LCA
    return up[u][0];
}

int main() {
    // 构造一棵简单的树，节点编号 0~6，0 为根
    int n = 7;
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);
    adj[2].push_back(5); adj[5].push_back(2);
    adj[2].push_back(6); adj[6].push_back(2);

    depth[0] = 0;
    dfs(0, -1);   // 根节点的父节点设为 -1

    cout << "节点3和节点4的LCA是: " << lca(3,4) << "\n";   // 应该是1
    cout << "节点3和节点5的LCA是: " << lca(3,5) << "\n";   // 应该是0
    return 0;
}

运行结果：

节点3和节点4的LCA是: 1
节点3和节点5的LCA是: 0

生活中的例子：找两个同学的“班级共同负责人”

假设班级里有一个组织结构树：班长是根，下面有组长，组长下面有组员。你想找两个组员的共同上级负责人（比如两个组员分别在不同小组，但属于同一个大组）。LCA 就是那个最近的共同负责人。

比如小明（节点3）和小红（节点4）都在第一组（节点1）下面，那么他们的 LCA 就是组长（节点1）。
小明（节点3）和小强（节点5）分别属于第一组和第二组，他们的 LCA 就是班长（节点0）。

这和我们代码里的例子完全一致。

新手容易犯的错误

忘记初始化 up 数组：比如没有把根节点的父节点设为 -1，或者没有给所有节点的 up[u][0] 赋值，导致后续祖先计算出现野指针或无效访问。
LOG 取值不够：如果节点数有 1000，LOG 至少需要 10（2^10=1024）。如果节点数有 100000，LOG 至少要 17（2^17=131072）。通常取 LOG = (int)log2(MAXN) + 2 比较安全。
在 DFS 中访问子节点时忘记跳过父节点：会导致死循环或错误。
查询时没判断 u == v：如果两个节点相同，直接返回即可，否则后面的循环可能会出错。
混淆深度定义：深度从根开始算，根深度为 0。如果你习惯从 1 开始，要在代码中统一。

完整可运行代码（带更多注释）

下面是一个完整可运行的代码，加上了输入输出示例，适合直接复制到本地 Dev-C++ 或 VS Code 中运行。树的结构可以自己改。

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

const int MAXN = 1000;      // 最大节点数，可自己改
const int LOG = 10;         // 2^10 = 1024

vector<int> adj[MAXN];      // 邻接表
int up[MAXN][LOG];          // 祖先表
int depth[MAXN];            // 深度

// DFS 预处理
void dfs(int u, int p) {
    up[u][0] = p;               // 父节点
    for (int k = 1; k < LOG; ++k) {
        if (up[u][k-1] != -1)
            up[u][k] = up[ up[u][k-1] ][k-1];
        else
            up[u][k] = -1;
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 深度差跳二进制
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; ++k) {
        if (diff & (1 << k)) {
            u = up[u][k];
        }
    }
    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];
        }
    }
    return up[u][0];   // 此时父节点就是LCA
}

int main() {
    // 手动构造一棵树（0为根），你也可以改成读入n和边
    int n = 7;
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);
    adj[2].push_back(5); adj[5].push_back(2);
    adj[2].push_back(6); adj[6].push_back(2);

    depth[0] = 0;
    dfs(0, -1);

    cout << "节点3和节点4的LCA是: " << lca(3,4) << "\n";
    cout << "节点3和节点5的LCA是: " << lca(3,5) << "\n";
    cout << "节点4和节点6的LCA是: " << lca(4,6) << "\n";
    return 0;
}

最近公共祖先（LCA）