树上倍增下的 LCA 问题

George222 / 2025-01-25 / 原文

LCA，最近公共祖先问题。

给定一颗有根树，若节点 k 既是节点 x 的祖先，又是节点 y 的祖先，则称 k 是 $\lbrack x, y \rbrack$ 的公共祖先。在 $\lbrack x, y \rbrack$ 的所有公共祖先中，深度最大的称为最近公共祖先，记作 $\operatorname*{LCA}(x, y)$。

$\operatorname*{LCA}(x, y)$ 即为节点 $x \rightarrow 1$ 和节点 $y \rightarrow 1$ 的第一个中途交汇点。

因为讲解倍增，所以这里使用 树上倍增法 求解。

设 $f_{x, k}$ 表示从 $x$ 节点走 $2^k$ 步到达的祖先节点，若此节点不存在则设 $f_{x, k} = 0$；显然，$f_{x, 0}$ 就是 $x$ 的父节点。

由于 $f_{i, j}$ 可以从 $f{i, j - 1}$ 走 $2^{j - 1}$ 步转移过来，所以得出神奇小公式：$\text{if } k \in \lbrack 1, \log n \rbrack, f_{x, k} = f_{f_{x, k - 1}, k - 1}$

要解决这个问题，我们还要求出每个节点的深度，可以使用 dfs 解决。

在处理 LCA 时，我们以 $\lbrack x, y \rbrack$ 中深度较大的开始，先使深度较大的缩短到最接近另一个深度的节点（自己 / 最近的祖先），然后一直向上即可。

完整代码：

#include <bits/stdc++.h>
#define int long long
#define il inline
using namespace std;

il int read()
{
    int x = 0;
    char c = getchar();
    while (c < '0')
        c = getchar();
    while (c >= '0')
    {
        x = x * 10 + (c - '0');
        c = getchar();
    }    
    return x;
}

int n, m, s;
vector<int> edge[500005];
int lca[500005][25], dep[500005];
void dfs(int x, int fa)
{
    lca[x][0] = fa;
    dep[x] = dep[fa] + 1;
    int now = edge[x].size();
    for (int i = 0; i < now; i++)
    {
        if (edge[x][i] == fa)
            continue;
        dfs(edge[x][i], x);
    }
    return ;
}
void pre()
{
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
            lca[i][j] = lca[lca[i][j - 1]][j - 1];
    }
    return ;
}
il int LCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[lca[x][i]] >= dep[y])
            x = lca[x][i];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
    {
        if (lca[x][i] != lca[y][i])
            x = lca[x][i], y = lca[y][i];
    }
    return lca[x][0];
}
signed main()
{
    n = read(); m = read(); s = read();
    for (int i = 1; i < n; i++)
    {
        int x, y;
        x = read(); y = read();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(s, 0);
    pre();
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        x = read(); y = read();
        cout << LCA(x, y) << "\n";
    }
    return 0;
}

时间复杂度：$O(m \log n)$。

注：本代码用于 AC lg P3379 模板问题。