C++ 实现最近公共祖先

admin

[mw_shl_code=cpp,true]#include<bits/stdc++.h>
using namespace std;
const int mxN(5e5),mxLg(19);
int n,q,rt,fa[mxLg+1][mxN+5],dep[mxN+5];
vector<int>nd[mxN+5];
void add(int u,int v){nd.push_back(v);}
void dfs(int u,int pr){
        fa[0]=pr,dep=dep[pr]+1;
        for(int i(1);i<=mxLg;++i)fa=fa[i-1][fa[i-1]];
        for(int i(0);i<nd.size();++i)if(nd!=pr)dfs(nd,u);
}
int LCA(int u,int v){
        if(dep<dep[v])swap(u,v);
        for(int i(mxLg);i>=0;--i){
                if(dep[fa]>=dep[v])u=fa;//如果要更新答案,要先更新再跳.
                if(u==v)return u;
        }
        for(int i(mxLg);i>=0;--i)if(fa!=fa[v])u=fa,v=fa[v];//等于0也是相同的.
        return fa[0];//不是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;
}[/mw_shl_code]