最近公共祖先 倍增算法

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> g[N];
int dep[N], fa[N][22];
void dfs(int u, int father) {
	dep[u] = dep[father] + 1;
	fa[u][0] = father;//2的i次方的点
	for (int i = 1; i <= 19; i++) {//跳跃
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (auto v : g[u]) {
		if (v == father) continue;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(v, u);//让u为深度最大的点
	for (int i = 19; i >= 0; i--) {
		if (dep[fa[u][i]] >= dep[v])//达到与v等深
			u = fa[u][i];
	}
	if (v == u) return v;
	for (int i = 19; i >= 0; i--) {
		if (fa[u][i]!= fa[v][i])//防止跳过
			u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];//返回他们的父亲【公共祖先】
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
	int n, m, S;
	cin >> n >> m >> S;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(S, 0);
	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << '\n';
	}
	return 0;
}