RT

$O(MN)$ 暴力不吸氧 最慢的点878ms，时限1.5s

https://www.luogu.com.cn/record/51826312

#include<iostream>
#include<cstdio>
using namespace std;
const int N=500005;
inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
int n,m,s,head[N],to[N<<1],nxt[N<<1],cnt,f[N],dep[N];
inline void add(int x,int y){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;return;}
void dfs(int x){
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=f[x]){
		f[to[i]]=x;dep[to[i]]=dep[x]+1;
		dfs(to[i]);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=f[x];
	while(x!=y)	x=f[x],y=f[y];
	return x;
}
int main(){
	n=read();m=read();s=read();
	for(int i=1,x,y;i<n;++i){x=read();y=read();add(x,y);add(y,x);}
	f[s]=s;dfs(s);
	for(int i=1,x,y;i<=m;++i){x=read();y=read();printf("%d\n",lca(x,y));}
}