最近公共祖先

#include <bits/stdc++.h>
using namespace std;
const int K = 20;
const int N = 5E5 + 5 , M = N * 2;

int head[N],ver[M],nxt[M],tot; 
int dep[N],bz[N][K];

void add(int x,int y) {
	ver[++tot] = y , nxt[tot] = head[x] , head[x] = tot;
}
void bfs(int x) {
	
	queue<int> q;
	q.push(x);
	dep[x] = 1; //注意这里 dep[x] = 1 , 防止 bfs 中 if(!dep[v]) 判断 , dep[root] = 0 时会重新入队
	
	
	while(q.size()) {
		int u = q.front(); q.pop();
		for(int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			if(!dep[v]) {
				dep[v] = dep[u] + 1;
				bz[v][0] = u;
				for(int j = 1 ; j < K ; ++j)
					bz[v][j] = bz[bz[v][j - 1]][j - 1];
				q.push(v);
			}
		}
	}
}
int lca(int x,int y)
{
	if(dep[x] < dep[y]) swap(x , y);
	
	for(int i = K - 1 ; i >= 0 ; --i) {
		if(dep[x] - dep[y] >= (1 << i)) // 同时注意写法 if(dep[bz[x][i]] >= dep[y]) , 这里 dep[root] = 0 时 , 会出错
			x = bz[x][i];
	}
	
	for(int i = K - 1 ; i >= 0 ; --i) {
		if(bz[x][i] != bz[y][i])
			x = bz[x][i] , y = bz[y][i];
	}
	
	if(x != y) {
		x = bz[x][0] , y = bz[y][0];
	}
	
	return x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	int n,m,s;
	cin >> n >> m >> s;
	
	for(int i = 0 ; i < n - 1 ; ++i) {
		int x,y;
		cin >> x >> y;
		add(x , y) , add(y , x);
	}
	
	bfs(s);	
	
	while (m--) {
		int x,y;
		cin >> x >> y;
		cout << lca(x , y) << '\n';
	}
	return 0;
}