C++ 实现最近公共祖先
#include<bits/stdc++.h>using namespace std;
const int mxN(5e5),mxLg(19);
int n,q,rt,fa,dep;
vector<int>nd;
void add(int u,int v){nd.push_back(v);}
void dfs(int u,int pr){
fa=pr,dep=dep+1;
for(int i(1);i<=mxLg;++i)fa=fa];
for(int i(0);i<nd.size();++i)if(nd!=pr)dfs(nd,u);
}
int LCA(int u,int v){
if(dep<dep)swap(u,v);
for(int i(mxLg);i>=0;--i){
if(dep]>=dep)u=fa;//如果要更新答案,要先更新再跳.
if(u==v)return u;
}
for(int i(mxLg);i>=0;--i)if(fa!=fa)u=fa,v=fa;//等于0也是相同的.
return fa;//不是u.
}
int main(){
scanf("%d%d%d",&n,&q,&rt);
for(int i(1),u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(rt,0);int u,v;
while(q--)scanf("%d%d",&u,&v),printf("%d\n",LCA(u,v));
return 0;
}
页:
[1]