「Day-4 提高笔记-LCA最近公共祖先」

#include<iostream>
using namespace std;

const int MAXN = 5 * 1e5 + 5;
struct node{
	int to,next;
}e[MAXN * 2];
int f[MAXN][20],dp[MAXN];//f[x][i] 表示 x 的第2^i个节点的编号 
int h[MAXN * 2],tot = 0;
int n,m,s;
void add(int x,int y){
	e[++ tot] = {y,h[x]};
	h[x] = tot;
}
void dfs(int x,int fa){
	dp[x] = dp[fa] + 1;
	f[x][0] = fa;//f[x][0] = x的第1(2^0)个父节点的节点编号 
	for(int i = 1;(1 << i) <= dp[x];i ++){
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for(int i = h[x];i;i = e[i].next){
		int to = e[i].to;
		if(to != fa){
			dfs(to,x);
		}
	}
	return;
}
int u,v;
int LCA(int x,int y){
	if(dp[x] < dp[y]) swap(x,y);
	for(int i = 19;i >= 0;i --){
		if(dp[x] - (1 << i) >= dp[y]){
			x = f[x][i];
		}
	}
	if(x == y) return x;
	for(int i = 19;i >= 0;i --){
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	} 
	return f[x][0];
}

int main(){
	cin >> n >> m >> s;
	for(int i = 1;i <= n - 1;i ++){
		cin >> u >> v;
		add(u,v); add(v,u); 
	}
	dfs(s,0);
	for(int i = 1;i <= m;i ++){
		cin >> u >> v;
		cout << LCA(u,v) << '\n';
	}
	return 0;
}