简介

最近公共祖先（Least Common Ancestors，简称 LCA）。

节点 $p,q$ 的最近公共祖先 $s$ 是这棵树中到 $p,q$ 的距离之和最小的节点。

如何求两个节点的 LCA？

$p,q$ 两个指针分别指向这两个节点，并且 $p$ 的深度比 $q$ 深。

将 $p$ 不断往父节点方向移，直到 $p,q$ 处于同一深度。

$p$ 和 $q$ 同时往父节点移，直到它们相遇于 $s$ 节点。$s$ 节点为 $p$ 和 $q$ 的 LCA。

	暴力算法（$\times$）	LCA 算法（$\surd$）
预处理	$0$	$O(n)$
单次查询	$O(n)$	$O(\log n)$
$m$ 次查询	$O(mn)$	$O(m\log n)$

int d[]; // d[u]: 节点 u 的深度
int f[]; // f[u]: 节点 u 的父节点

int LCA(int p, int q) {
    if (d[p] < d[q]) swap(p, q);         // 使 p 的深度 ≥ q
    while (d[p] > d[q]) p = f[p];        // 步骤 1
    while (p != q) p = f[p], q = f[q];   // 步骤 2
    return p;
}

原理

暴力算法慢在哪里？

-- $p$ 和 $q$ 每次只能向父节点跳一步！这是因为我们只保存了每个节点的父节点。

进一步思考，开一个二维数组 $f$：$f[p,i]$ 表示 $p$ 的第 $2^i$ 级父节点。

一张图中最多有 $2^{24}$ 个节点，否则光是读入这张图都会超时。因此数组只要开到 $f[n,25]$。

第一步

如果已经预处理出了 $f$ 数组，如何让 $p$ 向上跳到和 $q$ 同样深的位置？

采用「试跳法」。枚举 $i=24\to 0$：

• 若 $f[p,i]$ 的深度小于 $q$ 的深度，会跳过头，所以选择不跳；
• 否则就令 $p=f[p,i]$。

为什么要从 $24$ 开始枚举 $i$ 呢？因为 $p$ 不可能有超过 $2^{24}$ 级的父节点。

时间复杂度为 $O(24)$。

for (int i = 24; i >= 0; i --)
    if (d[f[p][i]] < d[q]) continue;
    else p = f[p][i];

第二步

令 $p$ 和 $q$ 同时往父节点跳，直到它们相遇。

仍然使用「试跳法」，枚举 $i=24\to 0$：

• 若 $f[p,i]=f[q,i]$，此时 $p,q$ 同时向上跳 $2^i$ 步会相遇，但是我们选择不跳；
• 若 $f[p,i]\ne f[q,i]$，令 $p=f[p,i],q=f[q,i]$，此时 $p,q$ 离相遇又近了一步。

枚举结束时，$p$ 和 $q$ 处于相遇和不相遇的临界状态，如下图。$p$ 或 $q$ 的父节点就是 LCA。

for (int i = 24; i >= 0; i --) {
    if (f[p][i] != f[q][i]) {
        p = f[p][i];
        q = f[q][i];
    }
}

合并两个步骤，得到求 LCA 的代码：

const int LogN = 24;

int LCA(int x, int y) {
    if (d[x] < d[y])
        swap(x, y);
    for (int i = LogN; i >= 0; i --) {
        if (d[f[x][i]] >= d[y]) x = f[x][i];
        if (x == y) return x; // 如果已经相遇，x 和 y 就是 LCA
    }
    for (int i = LogN; i >= 0; i --) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0]; // 返回的是父节点
}

预处理

出于 LCA() 函数的需要，我们还需要预处理：

• 每个节点的深度 $d[u]$；
• $f$ 数组。

首先 $d[u]=d[u$ 的父节点$]+1$，我们可以用一次深搜搞定 $d$ 数组。

$u$ 的 $2^{i+1}$ 级父节点，同时也是「$u$ 的 $2^i$ 级父节点」的 $2^i$ 级父节点。

$$f[u,i+1]=f[f[u,i],i]$$

计算顺序：$f[u,1\to 24]$。

如果你还不理解为什么要终止于 $f[u,24]$，请仔细再看一遍 原理。

采用 树形 DP 方法进行预处理。时间复杂度为 $O(24n)$。

const int N = 1e6, LogN = 24;
int n, d[N + 1], f[N + 1][LogN + 1];
vector<int> g[N + 1]; // g[u]: 与节点 u 相连的点集合

void pre(int u, int fa) { // u 的父节点是 fa
    f[u][0] = fa;
    d[u] = d[fa] + 1;
    for (int i = 0; i < LogN; i ++)
        f[u][i + 1] = f[f[u][i]][i];
    for (int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        if (v == fa) continue;
        pre(v, u);
    }
}

int main() {
    /* ...省略数据的输入... */
    pre(root, 0); // root 为根节点，如果题目没指定，可以为任意节点
}

模板

const int N = 1e6, LogN = 24;
int n, d[N + 1], f[N + 1][LogN + 1];
vector<int> g[N + 1];

void pre(int u, int fa) {
    f[u][0] = fa;
    d[u] = d[fa] + 1;
    for (int i = 0; i < LogN; i ++)
        f[u][i + 1] = f[f[u][i]][i];
    for (int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        if (v == fa) continue;
        pre(v, u);
    }
}

int LCA(int x, int y) {
    if (d[x] < d[y])
        swap(x, y);
    for (int i = LogN; i >= 0; i --) {
        if (d[f[x][i]] >= d[y]) x = f[x][i];
        if (x == y) return x;
    }
    for (int i = LogN; i >= 0; i --) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}