#include <bits/stdc++.h>
using namespace std;
int n, m, s;
struct D {
int d;
int f[22];
} a[500005];
vector<int> e[500005];
void dfs (int x) {
a[x].d = a[a[x].f[0]].d + 1;
for (int i = 0; i < e[x].size(); i++) {
if (e[x][i] != a[x].f[0]) {
a[e[x][i]].f[0] = x;
dfs(e[x][i]);
}
}
}
void init () {
for (int i = 1; i <= 20; i++) {
for (int j = 1; j <= n; j++) {
if (a[j].d >= (1 << i)) {
a[j].f[i] = a[a[j].f[i - 1]].f[i - 1];
}
}
}
}
int lca (int x, int y) {
if (a[x].d > a[y].d) {
swap(x, y);
}
for (int i = 20; i >= 0; i--) {
if ((a[y].d - a[x].d) >= (1 << i)) {
y = a[y].f[i];
}
}
if (x == y) {
return x;
}
for (int i = 20; i >= 0; i--) {
if (a[x].f[i] != a[y].f[i]) {
x = a[x].f[i], y = a[y].f[i];
}
}
return a[x].f[0];
}
int main () {
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(s);
init();
while (--m) {
int x, y;
cin >> x >> y;
cout << lca(x, y) << '\n';
}
return 0;
}
标签:祖先,LCA,back,dfs,int,init,公共,--,500005
From: https://www.cnblogs.com/hzt0/p/LeastCommonAncestors.html