洛谷 P3379 【模板】最近公共祖先(LCA)

题目链接:https://www.luogu.org/problemnew/show/P3379

LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。 ———来自百度百科 

倍增算法

所谓倍增,就是按2的倍数来增大,也就是跳 1、2、4 、8 、16、32 …… 不过在这我们不是按从小到大跳,而是从大向小跳,即按……、32、16、8、4、2、 1、如果大的跳不过去,再把它调小。这是因为从小开始跳,可能会出现“悔棋”的现象。拿 5 为例,从小向大跳,5≠1+2+4,所以我们还要回溯一步,然后才能得出5=1+4;而从大向小跳,直接可以得出5=4+1。这也可以拿二进制为例,5(101),从高位向低位填很简单,如果填了这位之后比原数大了,那我就不填,这个过程是很好操作的。

还是以 17 和 18 为例:

17->3

18->5->3

可以看出向上跳的次数大大减小了。这个算法的时间复杂度为O(nlogn),已经可以满足大部分的需求了。

想要实现这个算法,首先我们要记录各个点的深度和他们2^i级的的祖先,用数组\rm{deepth}表示每个节点的深度,fa[i][j]表示节点i2^j级祖先。 代码如下:

void dfs(int f,int fath) //f表示当前节点,fath表示它的父亲节点
{
deepth[f]=deepth[fath]+1;
fa[f][0]=fath;
for(int i=1;(1<<i)<=deepth[f];i++)
  fa[f][i]=fa[fa[f][i-1]][i-1]; //这个转移可以说是算法的核心之一
                                //自己好好揣摩吧233
for(int i=head[f];i;i=e[i].nex)
  if(e[i].t!=fath)
    dfs(e[i].t,f);
}

预处理完毕后,我们就可以去找它的LCA了,为了让它跑得快一些,我们可以加一个常数优化(来自洛谷提高组讲义)

for(int i=1;i<=n;i++) //预先算出log_2(i)+1的值,用的时候直接调用就可以了
  lg[i]=lg[i-1]+(1<<lg[i-1]==i);

接下来就是倍增LCA了,我们先把两个点提到同一高度,再统一开始跳。

但我们在跳的时候不能直接跳到它们的LCA,因为这可能会误判,比如 4 和 8,在跳的时候,我们可能会认为 1 是它们的LCA,但 1 只是它们的祖先,它们的LCA其实是 3 。所以我们要跳到它们LCA的下面一层,比如 4 和 8 ,我们就跳到 4 和 5,然后输出它们的父节点,这样就不会误判了。

int lca(int x,int y)
{
if(deepth[x]<deepth[y]) //用数学语言来说就是:不妨设x的深度 > y的深度
  swap(x,y);
while(deepth[x]>deepth[y])
  x=fa[x][lg[deepth[x]-deepth[y]]-1]; //先跳到同一深度
if(x==y)  //如果x是y的祖先,那他们的LCA肯定就是x了
  return x;
for(int k=lg[deepth[x]];k>=0;k--) //不断向上跳(lg就是之前说的常数优化)
  if(fa[x][k]!=fa[y][k])  //因为我们要跳到它们LCA的下面一层,所以他们肯定要不相等,如果不相等我们就跳过去。
    x=fa[x][k], y=fa[y][k];
return fa[x][0];  //返回父节点
}

题解转自https://www.luogu.org/blog/34188/solution-p3379
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int t,next;
}edge[1000010];
int n,m,s;
int cnt;
int head[500050],deep[500050],fa[500050][22],lg[500050];

void add(int x,int y)
{
    edge[cnt].t=y;
    edge[cnt].next=head[x];
    head[x]=cnt++;
}

void dfs(int f,int fath)//求深度
{
    deep[f]=deep[fath]+1;
    fa[f][0]=fath;
    for(int i=1;(1<<i)<=deep[f];i++)
        fa[f][i]=fa[fa[f][i-1]][i-1];//2^i=2^(i-1)+2^(i-1)
    for(int i=head[f];i!=-1;i=edge[i].next)
    {
        if(edge[i].t!=fath)//限制单向遍历
            dfs(edge[i].t,f);
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y])//保证x>=y
    {
        swap(x,y);
    }
    while(deep[x]>deep[y])//让x与y深度相同
    {
        x=fa[x][lg[deep[x]-deep[y]]-1];
    }
    if(x==y)
        return x;
    for(int k=lg[deep[x]];k>=0;k--)//向上跳
    {
        if(fa[x][k]!=fa[y][k])//直到相等后靠k减小逼近到lca
        {
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&s);
    cnt=0;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(s,0);
    for(int i=1;i<=n;i++)//常数优化,预处理log2()
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

4 thoughts on “洛谷 P3379 【模板】最近公共祖先(LCA)”

      1. 建议分开打,要采用面向对象程序设计
        void dfs(int u,int pre,int depth,int dis)
        {
        ans[u][0]=pre;
        d[u]=dis;
        deep[u]=depth;
        int len=mmp[u].size();
        for(int i=0; i<len; i++)
        {
        int v=mmp[u][i].v;
        if(v==pre)continue;
        dfs(v,u,depth+1,dis+mmp[u][i].w);
        }
        }
        void init()
        {
        for(int j=1; (1<<j)<n; j++)
        {
        k=j;
        for(int i=1; i<=n; i++)
        {
        ans[i][j]=-1;
        int temp=ans[i][j-1];
        if(temp==-1)
        continue;
        ans[i][j]=ans[temp][j-1];
        }
        }
        }

发表评论

电子邮件地址不会被公开。 必填项已用*标注