题解：P3379 【模板】最近公共祖先（LCA）

· · 题解

算法介绍

本题解介绍倍增法求 LCA。

倍增法

倍增法的本质是通过已知的一段内容，将该内容求解的范围扩大一倍，进而求解整个问题，从而提升程序效率。

倍增法求解 LCA

我们令 f_{i,j} 表示节点 i 向上跳 2^j 步，所到的节点。显然，f_{i,0} 表示节点 i 的父亲节点。

现在有了初始化，那么我们就有了求解所有 f_{i,j} 的基础。想要求解每一个 i 节点跳 2^j 到的节点，等同于 i 节点先往上跳 2^{j-1} 步到的节点，再往上跳 2^{j-1} 步到的最终节点。由上述描述，可得递推式：

f_{i,j} = f_{f_{i,j-1},j-1}

注意，往上跳的过程中，不能跳出根节点。

求解 LCA 时，只需将两个节点拉直同一深度，如果两个节点相同，则返回两者之间任一节点，否则一起往上跳相同步数直至求出 LCA 为止。

正确性证明

时间复杂度证明

预处理时，对于 n 个节点在不跳出根节点的情况下，每次最多循环 \log n 次。预处理复杂度 O(n \log n)。

每次查询时，最坏情况下两个深度最高的节点的 LCA 是根节点，拉至 LCA 的总时间复杂度为 O(\log n)。

递推式证明

如果程序在求解 1 到 n 跳跃 2^j 步达到的节点，必然求解了 1 到 n 跳跃 2^{j-1} 步的节点。所以递推式正确。

本棵树边界条件是条链，因此，一个节点最多跳的步数小于 n。

查询证明

一个节点到另一个节点的深度是唯一确定的，因此跳跃的步数也是唯一确定的。所以相同深度的两个节点到 LCA 的步数也是相同的。而我们已经用倍增法记录下了每个 f_{i,j}，所以该算法是正确的。

代码实现

对于每一个节点 i 求 f_{i,0}，我们可以直接用 DFS 求解，并记录下此时节点 i 的深度以及 f_{i,0}。代码如下：

inline void dfs (int u, int fa) {
    f[u][0] = fa;//记录父亲节点
    dep[u] = dep[fa] + 1;//记录深度
    for (auto v : e[u])
        if (v != fa) dfs (v, u);
}

对于求解每一个 f_{i,j}，代码如下：

inline void init () {
    for (int j = 1; (1 << j) <= n; ++j)//边界范围
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
}

接下来是核心的求解 LCA，代码如下：

inline int lca (int u, int v) {
    if (dep[u] < dep[v]) swap (u, v);
    for (int i = 22; i >= 0; i--) {
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    }//跳至同一深度
    if (u == v) return u;//此时节点为 LCA
    for (int i = 22; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }//一起往上跳
    return f[u][0];
}

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n, m, s, f[N][33], dep[N];
vector <int> e[N];
bool vis[N];
inline void dfs (int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (auto v : e[u])
        if (v != fa) dfs (v, u);
}//求 f[i][0]
inline int lca (int u, int v) {
    if (dep[u] < dep[v]) swap (u, v);
    for (int i = 22; i >= 0; i--) {
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
    if (u == v) return u;
    for (int i = 22; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}//求两个节点的 LCA
inline void init () {
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
}//求 f[i][j]
int main () {
    ios :: sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n >> m >> s;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        e[x].push_back (y);
        e[y].push_back (x);
    }
    dfs (s, 0);
    init ();
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        cout << lca (u, v) << "\n";
    }
    return 0;
}