#include <bits/stdc++.h>
using namespace std;
int n,m,r,k,f[500010][50],d[500010];
vector<int> v[500010];
void dfs(int x,int deep){
d[x]=deep;
for(int i=0;i<v[x].size();i++){
if(d[v[x][i]]!=0) continue;
f[v[x][i]][0]=x;
dfs(v[x][i],deep+1);
}
}
int lca_fuck_ccf(int x,int y){
if(d[x]<d[y]){
swap(x,y);
}
for(int i=log2(n);i>=0;i--){
if(d[f[x][i]]>=d[y]){
x=f[x][i];
}
}
if(x==y){
return x;
}
for(int i=log2(n);i>=0;i--){
if(f[x][i]==f[y][i]) continue;
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main(){
cin>>n>>m>>r;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(r,1);
k=log2(n);
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
while(m--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca_fuck_ccf(x,y));
}
return 0;
}
倍增LCA
发布时间 2023-11-28 00:00:05作者: Zhao_zzZ