评测记录

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> tr[500001];
int dep[500001],f[500001][32];
int v[500001];
int c[500001];
using namespace std;
void dfs(int x,int y){
	v[x]=1;
	f[x][0]=y;
	dep[x]=dep[y]+1;
	for(int i=1;i<=31;i++)f[x][i]=f[f[y][i-1]][i-1];
	for(int i=0;i<tr[x].size();i++){
		if(!v[tr[x][i]]){
			dfs(tr[x][i],x);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=0;dep[x]!=dep[y];i++){
		if(dep[f[x][i]]<=dep[y]) x=f[x][i];
	}
	if(x==y) return x;
	for(int i=c[dep[x]-1];i>=0 && x!=y;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main(){
	int n,m,s,x,y;
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		tr[x].push_back(y);
		tr[y].push_back(x);
	}
	dfs(s,0);
	int tmp=1;
	for(int i=1;i<=500000;i++){
		if(i==tmp){
			tmp<<=1;
			c[i]=c[i-1]+1;
		}
		else c[i]=c[i-1];	
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
}