文件详细信息

下载本文件

本文件的大小为 1298 字节。

#include<cstdio>
#include<cstring>
#define maxn 500005
#define maxm 1000005
int n,m,s,count,total,head[maxn],to[maxm],next[maxm];
int size[maxn],depth[maxn],fa[maxn],son[maxn],top[maxn],tip[maxn],rank[maxn];
inline 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;
}
inline void add(int a,int b){
	to[++total]=b;
	next[total]=head[a];
	head[a]=total;
}
void dfs1(int x,int from){
	size[x]=1,depth[x]=depth[from]+1;
	for(int i=head[x];i;i=next[i]){
		int y=to[i];
		if(y!=from){
			fa[y]=x;
			dfs1(y,x);
			size[x]+=size[y];
			if(son[x]==-1||size[y]>size[son[x]])son[x]=y;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp;
	tip[x]=++count;
	rank[tip[x]]=x;
	if(son[x]==-1)return;
	dfs2(son[x],tp);
	for(int i=head[x];i;i=next[i]){
		int y=to[i];
		if(y!=son[x]&&y!=fa[x])dfs2(y,y);
	}
}
inline int lca(int a,int b){
	while(top[a]!=top[b])
		if(depth[top[a]]>depth[top[b]])a=fa[top[a]];
		else b=fa[top[b]];
	return depth[a]<depth[b]?a:b;
}
int main(){
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	memset(son,-1,sizeof(son));
	dfs1(s,0);
	dfs2(s,s); 
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		printf("%d\n",lca(x,y));
	}
	return 0;
}