文件详细信息

下载本文件

本文件的大小为 1184 字节。

#include<cstdio>
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
void swap(int&a,int&b){
	int temp=a;
	a=b;
	b=temp;
}
const int maxn=500005;
int log[maxn];
int n,m,s,x,y,u,v,total,head[maxn],to[maxn<<1],next[maxn<<1];
void add(int a,int b){
	to[++total]=b;
	next[total]=head[a];
	head[a]=total;
}
int depth[maxn],fa[maxn][20];
void dfs(int u,int from){
	depth[u]=depth[from]+1;
	fa[u][0]=from;
	for(int i=1;i<=log[depth[u]];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=next[i]){
		int v=to[i];
		if(v==from)continue;
		dfs(v,u);
	}
}
int lca(int x,int y){
	if(depth[x]<depth[y])swap(x,y);
	while(depth[x]>depth[y])x=fa[x][log[depth[x]-depth[y]]];
	if(x==y)return x;
	for(int i=log[depth[x]];i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main(){
	n=read(),m=read(),s=read();
	for(int i=2;i<=n;i++)
		if((i&(i-1))==0)log[i]=log[i-1]+1;
		else log[i]=log[i-1];
	for(int i=1;i<n;i++){
		u=read(),v=read();
		add(u,v);
		add(v,u); 
	}
	dfs(s,0);
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		printf("%d\n",lca(x,y));
	}
	return 0;
}