C++最近公共祖先算法LCA

        LCA算法是一种求树上最近公共祖先的算法。

        最近公共祖先：两个节点在树中深度最大的共同祖先节点。

例如：节点1和节点5的公共祖先有4、7，最近公共祖先是4。

           节点5和节点8的公共祖先有7，最近公共祖先是7。

核心

        实现LCA算法需要先通过倍增的方法求出数组f[i][j]（f[i][j]表示从节点i向上跳的第2^j个祖先节点的编号）。然后LCA算法的核心是一个点先跳，让后一起跳。

例题：给定一颗n个节点的树，m次询问，每次询问x,y求它们的最近公共祖先。

#include<bits/stdc++.h>
using namespace std;
const int N=5E5+10,L=20;
vector<int> a[N];
int dep[N];//节点的深度
int f[N][L];//节点i向上跳的第2^j个祖先节点的编号
int lg[N];//log2(i)

//初始化dfs
void dfs(int x,int fath){
f[x][0]=fath;//向上跳1层是父亲
dep[x]=dep[fath]+1;
for(int i=0;i<a[x].size();i++){
int y=a[x][i];
if(y!=fath)dfs(y,x);
}
}

//经典的lowbit函数,求二进制中最低位的1
int lowbit(int x){
return x&-x;
}

//求最近公共祖先
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);//x深度要大于y

//x先跳到和y同样深度的位置
int t=dep[x]-dep[y];
while(t){
int lt=lowbit(t);
t-=lt;
x=f[x][lg[lt]];
}
if(x==y)return x;//特判

//x，y一起向上跳相同的高度过程中x!=y
for(int i=L-1;i>=0;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;
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}

dfs(s,0);

//倍增求f
for(int j=1;j<L;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}

lg[1]=0;//从2开始！
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;

while(m–){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\\n",lca(x,y));
}

return 0;
}

        LCA预处理O(nlogn)，查询O(mlogn)，应用特别广。

        谢谢观看。