LCA 学习笔记

LCA 是最近公共祖先的简称。

朴素算法

如果两个点的深度相同：就往上跳，直到两个节点相同。

否则先让两个点的深度相同。

倍增

和朴素算法类似，只是把挨个往上跳变成每次跳 $2^i$。

代码：

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n, m, s;
vector <int> e[100005];
int dp[100005][25], de[100005];
//dp[i][j] 为 i 的上 2^j 代。
void dfs(int fa, int fafa) {
    for (int i = 1; i <= log2(de[fa]); i ++) {
        dp[fa][i] = dp[dp[fa][i - 1]][i - 1];
    }
    for (int i = 0; i < e[fa].size(); i ++) {
        int y = e[fa][i];
        if (y == fafa) continue;
        de[y] = de[fa] + 1;
        dp[y][0] = fa;
        dfs(y, fa);
    }
}
int lca(int x, int y) {
    if (de[x] > de[y]) swap(x, y);
    for (int i = log2(de[y] - de[x]); i >= 0; i --) {
        if (1 << i <= de[y] - de[x]) y = dp[y][i];
    }
    if (x == y) return x;
    else {
        for (int i = log2(de[x]); i >= 0; i --) {
            if (dp[x][i] != dp[y][i]) x = dp[x][i], y = dp[y][i];
        }
        return dp[x][0];
    } 
}
int main() {
    ios::sync_with_stdio(false); 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);
    }
    de[s] = 1;
    dfs(s, s);
    while (m --) {
        int x, y; cin >> x >> y; cout << lca(x, y) << "\n";
    }
    return 0;
}