倍增在线算法求最近公共祖先

倍增算法可以在线求树上两个点的LCA，预处理时间复杂度为 O(n log n)，查询复杂度O (log n)

倍增算法需要一个预处理过程，在dfs过程中求出每个节点v的深度deep[v] 和该节点上2^i的祖先节点f[v][i]

求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将连个节点同时上移，查询最近公共祖先。

 

下面是预处理过程
[cc lang=”C++”]
void dfs(int index){
f[index][0] = fa[index]; //index节点上1个祖先节点就是index的父亲

    for(int i=1;i<=MAXM;i++)
        f[index][i] = f[f[index][i-1]][i-1]; //倍增的体现

    for(int i=0;i<map[index].size();i++){
        int v = map[index][i];

        if(v != fa[index]){
            fa[v] = index; //记录父亲
            deep[v] = deep[index] +1 ; //记录深度

            dfs(v);
        }
    }
} 

[/cc]

 

LCA过程
[cc lang=”C++”]
int lca(int x,int y){
if(deep[x] < deep[y])
swap(x,y); //x为更深的节点

    for(int i=MAXM;i>=0;i--){
        if(deep[y] <= deep[f[x][i]]){ //注意等号(还未向上跳)
            x = f[x][i]; //使x和y在同一深度
        }
    }

    if(x==y)
        return x; //y是x的祖先

    for(int i=MAXM;i>=0;i--){
        if(f[x][i] != f[y][i]){
                            //一起向上跳，想象需要跳i下，那么i可以转化为二进制数字
            x = f[x][i];
            y = f[y][i];
                            //不要break了
        }
    }

    return f[x][0]; //此时他们父亲节点相等，所以返回父亲节点(判断语句)
}

[/cc]

MAXM = log(MAXN)
另外注意要将dfs的根节点的父亲赋值为根节点，否则若公共祖先为根节点的时候，会输出0

 

参考资料
sllr15 – 最近公共祖先