LCA（最近公共祖先）问题

问题描述

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

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

解法一：向上标记法

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

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

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

每次询问，最坏复杂度为O（n）

解法二：树上倍增法

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

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

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

倍增预处理

设F[x,k]表示x的2^k辈祖先。也就是，x向上跳2^k所到达的节点。如果跳到了一个压根不存在的节点，我们让他的值为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] ，因为 2^k-1+2^k-1=2* 2^k-1=2^k

预计需要的时间复杂度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=2^logn一直枚举到2⁰。为什么要倒着呢？因为要尽可能跳的次数少一点降低复杂度。

　　检查即将上跳到的节点是否比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];
}

用途

求树从x到y结点最短路径上所有节点的值之和

其实这是写这篇博文的目的…

怎么办呢？其实也只是个性质。即从根节点出发做一次单源最短路（或者直接Dfs）。那么Distance ( x , y ) = Distence ( x ) + Distence ( y ) - 2 * Distence ( Lca )

所以只需要O（n）求最短路径，再求个LCA即可。