RT

我的暴力直接过了，最快的点只跑了0.7s。。。

#include<cstdio>
#include<vector>
using namespace std;
int n,m,s,x,y,deep[500001],fa[500001];
vector<int>g[500001];
void dfs(int x,int y)
{
	deep[x]=y;
	for(int i=0;i<g[x].size();i++)
		if(deep[g[x][i]]==0)
			dfs(g[x][i],y+1);
}
void dfs2(int x)
{
	for(int i=0;i<g[x].size();i++)
		if(deep[g[x][i]]==deep[x]+1)
			fa[g[x][i]]=x,dfs2(g[x][i]);
}
int lca(int x,int y)
{
	int x1=x,y1=y;
	if(x==s||y==s)
		return s;
	for(int i=1;i<=max(0,deep[x1]-deep[y1]);i++)
		x=fa[x];
	for(int i=1;i<=max(0,deep[y1]-deep[x1]);i++)
		y=fa[y];
	while(x!=y)
		x=fa[x],y=fa[y];
	return x;
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(s,1);
	dfs2(s);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}