LCA算法的介绍与模板

对于一棵树，求两个节点的最近公共祖先（LCA）。

　　如下图：（以下数字代表对应编号的节点）

　　11 和 66 的 LCA 是 88 。

　　1111 和 11 的 LCA 是 88 。

　　1111 和 1515 的 LCA 是 44 。

　　1414 和 1313 的 LCA 是 11 。

以洛谷P3379模板题为例

方法一：用倍增来在线求 LCA ，时间和空间复杂度分别是 O((n+q)logn)O((n+q)log⁡n) 和 O(nlogn)O(nlog⁡n) 。

　　对于这个算法，我们从最暴力的算法开始：

　　　　①如果 aa 和 bb 深度不同，先把深度调浅，使他变得和浅的那个一样

　　　　②现在已经保证了 aa 和 bb 的深度一样，所以我们只要把两个一起一步一步往上移动，直到他们到达同一个节点，也就是他们的最近公共祖先了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=5e5+5;
int lg[maxn];//log 2n向下取整
const int maxbit=20;
vector<int>G[maxn];
int depth[maxn];//记录每个节点的深度
int father[maxn][maxbit];//father[i][j]指的是i节点往上2^j的节点 
void dfs(int nowp,int fa)
{
    depth[nowp]=depth[fa]+1;//当前节点深度是父节点深度+1
    father[nowp][0]=fa;
    for(int j=1;j<=lg[depth[nowp]];j++)//倍增求father 
     father[nowp][j]=father[father[nowp][j-1]][j-1];
    for(int i=0;i<G[nowp].size();i++)
    {
        if(G[nowp][i]!=fa)
        dfs(G[nowp][i],nowp);
    }
}
int LCA(int u,int v)
{
    if(depth[u]<depth[v])//维护u的深度最大
      swap(u,v);
     while(depth[u]!=depth[v])
     u=father[u][lg[depth[u]-depth[v]]];//使两个节点在同一高度；
     if(u==v)
     return u;
     for(int j=lg[depth[u]];j>=0;--j)
     {
         if(father[u][j]!=father[v][j])
         {
             u=father[u][j];
             v=father[v][j];
        }
     } //得到最近公共祖先下一位；
     return father[u][0];
}
int main()
{
    lg[0]=-1;
    for(int i=1;i<maxn;i++)
    lg[i]=lg[i>>1]+1;
    //dfs(s,0);//假设根结点的父节点为0； 
    int n,m,s;int x,y;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {

        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(s,0);//假设根结点的父节点为0；
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
     }
    return 0;
}