RT

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int depth;
	vector <int> son;
}a[500001];
int n,m,s,t1,t2;
int f[500001][16];
int dfs(int p,int fp,int d)
{
	a[p].depth=d,f[p][0]=fp;
	for(int i=1;i<=15;i++) 
		f[p][i]=f[f[p][i-1]][i-1];
	for(int i=0;i<a[p].son.size();i++)
	{
		if(a[p].son[i]!=fp)
			dfs(a[p].son[i],p,d+1);
	} 
}
int lca(int x,int y)
{
	if(a[x].depth<a[y].depth)
		swap(x,y); 
	for(int i=15;i>=0;i--) 
		if(a[f[x][i]].depth>=a[y].depth)
			x=f[x][i];
	if(x==y)
		return x;
	for(int i=15;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
//	freopen("P3379_1.in","r",stdin);
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=n-1;i++)
    {
    	scanf("%d %d",&t1,&t2);
    	a[t1].son.push_back(t2);
    	a[t2].son.push_back(t1);
	}
	dfs(s,0,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&t1,&t2);
		printf("%d\n",lca(t1,t2));
	}
    return 0;
}

写的倍增LCA 有人和我一样吗