P3379

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

70 WA+T

#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,vis[500010],dep[500010],dp[500010][100];
vector<int>g[500010];
void dfs(int u){
	for(int i=1;(i<<1)<dep[u];i++){
		dp[u][i]=dp[dp[u][i-1]][i-1];
	}for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v]==0){
			vis[v]=1;
			dep[v]=dep[u]+1,dp[v][0]=u;
			dfs(v);
		}
	}
}int LCA(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}for(int i=log2(dep[x]-dep[y]);i>=0;i--){
		if(dep[dp[x][i]]>=dep[y]){
			x=dp[x][i];
		}
	}if(x==y){
		return x;
	}for(int i=log2(dep[x]);i>=0;i--){
		if(dp[x][i]!=dp[y][i]){
			x=dp[x][i],y=dp[y][i];
		}
	}return dp[x][0];
}int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}dep[s]=1,vis[s]=1;
	dfs(s);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		printf("%d\n",LCA(u,v));
	}return 0;
}