TLE

#include <iostream>
#include <cstring>
using namespace std;
int a[1200000],al[1200000],head[500010],an=0;
int father[500010][21],depth[500010];
bool visit[500010];
int logchart[500010];
int n,q,s;
void addline(int u,int v){
	a[an]=v;al[an]=head[u];head[u]=an;
	an++;
}
void logchart_build()
{
    logchart[1]=0;
    logchart[2]=1;
    for(int i=3;i<=n;i++)
        logchart[i]=logchart[i/2]+1;
}
inline void dfs_buildchart(int u,int dep){
	visit[u]=1;
	depth[u]=dep;
	int i,j,k,l,v;
	for(i=1;i<=logchart[dep];i++)
		father[u][i]=father[father[u][i-1]][i-1];
	for(l=head[u];l!=-1;l=al[l]){
		v=a[l];
		if(visit[v]==0){
			father[v][0]=u;
			dfs_buildchart(v,dep+1);
		}
	}
}
inline int find(int u,int gener){
	int i,j,k,l,ans;
	k=logchart[gener];
	if(gener-k>0){
		ans=find(father[u][k],gener-(1<<k));
	}
	else ans=u;
	return ans;
}
inline int lca(int u,int v){
	int i,j,k,l,ans=0;
	if(depth[u]<depth[v])v=find(v,depth[v]-depth[u]);
	else if(depth[u]>depth[v])u=find(u,depth[u]-depth[v]);
	bool tag=0;
	for(i=logchart[depth[u]];i>=0;i--){
		if(father[u][i]!=father[v][i]){
			tag=1;
			ans=lca(father[u][i],father[v][i]);
		}
	}
	if(tag==0&&u!=v)ans=father[u][0];
	if(tag==0&&u==v)ans=u;
	return ans;
}
int main(){
	memset(al,-1,sizeof(al));
	memset(head,-1,sizeof(head));
	memset(visit,0,sizeof(visit));
	int i,j,k,l;
	cin>>n>>q>>s;
	int u,v;
	for(i=1;i<=n-1;i++){
		cin>>u>>v;
		addline(u,v);addline(v,u);
	}
	logchart_build();
	dfs_buildchart(s,1);
	for(i=1;i<=q;i++){
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
	return 0;
}