LCA(最近公共祖先)问题

问题描述

在一棵树中,如果某个节点z是节点x的祖先(即节点z深度<节点x),也是y的祖先。那么称节点z是x与y的公共祖先。

那顾名思义,所谓最近公共祖先,就是对于x和y来说距离之和最近的公共祖先。

解法一:向上标记法

除非你发了高烧啥都不会打,否则换方法

从x节点向上走到根节点,把所有经过的节点标记。

从y节点向上走,第一次遇到被标记过的节点的时候,该节点为所求点。

每次询问,最坏复杂度为O(n)

解法二:树上倍增法

不温不火,很适合考场的时候打啊…

首先理解倍增算法。类似于动态规划思想

复杂度O((n+m)log n)

倍增预处理

设F[x,k]表示x的2k辈祖先。也就是,x向上跳2k所到达的节点。如果跳到了一个压根不存在的节点,我们让他的值为0。

显然根据定义,可以得出F[x,0]就是x的父节点。

为了不少跳,求出k的范围应当属于[1,logn]。在c++中,应写为

t=(int)log(n)/log(2)+1

接下来就有转移方程:

F[x,k]=F[F[x,k-1],k-1] ,因为 2k-1+2k-1=2* 2k-1=2k

预计需要的时间复杂度O(n logn)

void bfs(){
    q.push(1);
    d[1]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=Head[x];i;i=Next[i]){
            int y=End[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            f[y][0]=x;
            for(int j=1;j<=t;j++){
                f[y][j]=f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}

跳跃式处理LCA 

由上面的预处理,我们得到了已经初始化的D(深度)数组和F(倍增)数组

我们假定D[x]>=D[y]  (否则你就交换一下嘛)

1.让x往上跳,先跳到和y一样高再说

  怎么实现呢?枚举。枚举上跳步数。枚举jump=2logn一直枚举到20。为什么要倒着呢?因为要尽可能跳的次数少一点降低复杂度。

  检查即将上跳到的节点是否比y要低一点。如果是就完成上跳,即让x=F[x,jump]

2.如果发现仅仅完成第一步就有了x==y(x跳到y脸上去了),说明y本来就是x的祖先,那么LCA就等于y。

3.让x和y一起往上跳,保持两者深度相同但不相汇。依然按照步骤一一样去枚举jump。只要F[x,jump]不等于F[y,jump],就赋值起跳。

4.经过了步骤3的磨砺,x和y一定就差最后一步就可以相汇了。那么两者任意一个节点的父节点就必然是LCA(x,y)。所以此时LCA(x,y)=F[x,0]

int lca(int x,int y){
    if(d[x]>d[y]) swap(x,y);
    for(int i=t;i>=0;i--){
        if(d[f[y][i]]>=d[x]) y=f[y][i];
        if(x==y) return x;    
    }
    for(int i=t;i>=0;i--){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}

 

上一篇:LuoguP1967 货车运输 LCA


下一篇:H.蹦床跳跃(Jump Conveyor)