LCA学习笔记

建树

结点数为N 边数为M 根节点S

log2N 为树的最大深度

int log2N=log(1.0*N)/log(2.0)+0.5;

通过DFS预处理出树与深度

inline void dfs(int x,int f){
    V[x]=1;
    D[x]=D[f]+1;
    F[X][0]=f;
    for(int i=Last[x];i;i=e[i].next){
        if(V[x]) continue;
        dfs(e[i].to,x);
    }
}

朴素算法

DFS

复杂度O(N)

求LCA(A,B)

从A点DFS到根S，路径标记为为1

再尝试从B点DFS到根S 路径上第一个被标记为1的点即为所求

调点

设u，v中深度大的点为u

寻找u点与v点同一深度的祖先

查看u点和v点的父节点是否相同

相同返回父节点

不相同u与v变成各自的父节点(上提)

inline int LCA(int u,int v){
    if(D[u]<D[v]) 
        swap(u,v);
    while(D[u]>D[v]) 
        u=fa[u];
    while(u!=v){
        u=fa[u];
        v=fa[v];
    }
    return u;   
} 

倍增 + DP (在线)

倍增：每次跳2^x^ 个点

倍增数组F[i][j]:从i点开始朝根结点 走2^j^ 步所到达的点

F[i][j]=F[F[i][j-1]][j-1]

i 跳 2^j^ 步 是 i 跳了 2^(j-1)^ 步后的点再跳 2^(j-1)^ 步所到的点

2^j^=2*2^(j-1)^ 其中j<=log~2~N d[i]>=2^j^

for(int j=1;j<=log2n;++j)
    for(int i=1;i<=n;++i)
        if(d[i]>=(1<<j))
            f[i][j]=f[f[i][j-1]][j-1];

求LCA(X,Y)

设此时 D[X] > D[Y]

将 X 提到与 Y 同一深度的位置

即 X 在自己的祖先中 寻找一个与 Y 同一深度的祖先 T

for(int i=Log2N;i>=0;--i)
    if(D[X]>=D[Y])
        X=F[X][i];

如果 T == Y 那么 LCA(X,Y)=Y;

if(X==Y) return X;

如果 T != Y 那么 LCA(X,Y)=LCA(T,Y)

若求 X 与 Y 的公共祖先，只用求 T 与 Y 的公共祖先

for(int i=Log2N;i>=0;--i)
    if(F[X][i]!=F[Y][i])
        X=F[X][i],Y=F[Y][i];
return F[X][0];

Tarjan (离线)

懒得写了