LCA找祖宗

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,LOG=20;
vector<int>e[maxn];
int dep[maxn];//dep[u]表示节点u的深度
int f[maxn][LOG];//fa[u][k]表示节点u的2^k级祖先
int n,m,s;
//注意：如果u节点没有2^k级节点，则将其设成0
//DFS预处理每个结点的深度和倍增表
void dfs(int now,int last){
//动态规划预处理2^k级祖先(k从1到LOG-1)
for(int k=1;k<LOG;k++){
//u的2^{k祖先=(u的2}{k-1}祖先)的2^{k-1}祖先
f[now][k]=f[f[now][k-1]][k-1];
}
//递归处理子节点
for(int v : e[now]){
if (vlast) continue;
dep[v]=dep[now]+1;//深度=父节点深度+1
f[v][0]=now;//u的2^0级祖先即直接父节点
dfs(v,now);
}
}
//查询节点u和v的最近公共祖先(LCA)
int LCA(int u,int v){
//第一步：确保u是较深节点
if(dep[u]<dep[v]) swap(u,v);
//第二步：深度对齐(u上移至与v共同深度)
for(int k=LOG-1;k>=0;k--){
//若u能上移2^k层且不越过v的深度，则上移
if(dep[f[u][k]]>=dep[v]) u=f[u][k];
}
if(uv) return u;//此时v就是LCA
//第三步：同步上移找LCA
for(int k=LOG-1;k>=0;k--){
//若u和v的2^k祖先不同，则同步上移
if(f[u][k]!=f[v][k]) u=f[u][k],v=f[v][k];
}
return f[u][0];//最终u和v的父节点即为LCA
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dep[s]=1;
dfs(s,0);//从根节点开始DFS
while(m--){
int u,v;
cin>>u,v;
cout<<LCA(u,v)<<endl;
}
}