树上倍增下的 LCA 问题

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 模板问题。