倍增LCA

一个一个网上跳

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int f[N][30],d[N];
vector<int> G[N];
void dfs(int p,int fa)
{
	d[p]=d[fa]+1;
	f[p][0]=fa;
	for(int i=1;(1<<i)<=d[p];i++)
	f[p][i]=f[f[p][i-1]][i-1];
	for(int i=0;i<G[p].size();i++)
	if(G[p][i]!=fa)
	dfs(G[p][i],p);
}
int LCA(int x,int y)
{
	if(d[x]<d[y])
	swap(x,y);
	while(d[x]>d[y])
	x=f[x][(int)log2(d[x]-d[y])];
	if(x==y)
	return x;
	for(int i=log2(d[x]);i>=0;i--)
	if(f[x][i]!=f[y][i])
	x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	int n,m,s,l,r;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&l,&r);
		G[l].push_back(r);
		G[r].push_back(l);
	}
	dfs(s,s);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",LCA(l,r));
	}
}