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;
}
nice