P3379 【模板】最近公共祖先（LCA）

#include <bits/stdc++.h>
using namespace std;

int tot, n, m, s;
const int N = 5e5 + 10, M = 1e6 + 10;
int head[N], dep[N], fa[N][22];
struct Edge{
	int u, v, next;
}edge[M];

void add(int u, int v){
	edge[tot].v = v;
	edge[tot].next = head[u];
	head[u] = tot ++;
}

void dfs(int now, int pre){
	dep[now] = dep[pre] + 1;
	fa[now][0] = pre;
	for(int i = head[now]; i != -1; i = edge[i].next){
		int v = edge[i].v;
		if(v != pre)
			dfs(v, now);
	}
}

int getlca(int u, int v){
	if(dep[u] < dep[v])
		swap(u, v);
	while(dep[u] > dep[v])
		u = fa[u][(int)log2(dep[u] - dep[v])];
	if(u == v)
		return u;
	for(int j = 20; j >= 0; j --)
		if(fa[u][j] != fa[v][j])
			u = fa[u][j], v = fa[v][j];
	return fa[u][0];
}
int main(){
	cin >> n >> m >> s;
	memset(head, -1, sizeof head);
	for(int i = 1; i < n; i ++){
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}

	
	dfs(s, 0);

	for(int j = 1; j <= 20; j ++)			//次数从小到大更新 
		for(int i = 1; i <= n; i ++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	
	for(int i = 1; i <= m; i ++){
		int a, b;
		cin >> a >> b;
		int ans = getlca(a, b);
		cout << ans << endl;
	}
	return 0;
}