最近公共祖先（LCA）

简介 #

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

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

如何求两个节点的 LCA？

step 1

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

step 2

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

step 3

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

	暴力算法（$\textcolor{red}{×}$）	`LCA` 算法（$\textcolor{green}{√}$）
预处理	$\textcolor{green}{0}$	$\textcolor{green}{O(n)}$
单次查询	$\textcolor{red}{O(n)}$	$\textcolor{green}{O(\log{n})}$
$m$ 次查询	$\textcolor{red}{O(mn)}$	$\textcolor{green}{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→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→0$：

若 $f[p,i] = f[q,i]$，此时 $p,q$ 同时向上跳 $2^i$ 步会相遇，但是我们选择不跳.
若 $f[p,i] \not= 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→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];
}