最近公共祖先

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> G[500000+10];
ll n,m,root;
ll f[500000+10][20],dep[500000+10],lg[500000+10];
void dfs(ll u,ll fa){
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(ll i=1;dep[u]-(1<<i)>0;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(ll i=0;i<G[u].size();i++){
		ll v=G[u][i];
		if(v==fa)continue;
		dfs(v,u);
	}
}
ll lca(ll x,ll y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]];
	if(x==y)return x;
	for(ll i=lg[dep[x]-1];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 >> root;
	for(ll i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
	for(ll i=1;i<=n-1;i++){
		ll u,v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(root,0);
	for(ll i=1;i<=m;i++){
		ll x,y;
		cin >> x >> y;
		cout << lca(x,y) << endl;
	}
	return 0;
}