LCA算法

2021/7/23 1:06:30

编程Tag： 算法更新节点祖先 -- vis LCA

本文主要是介绍LCA算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LCA 即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

　　　　换句话说，就是两个点在这棵树上距离最近的公共祖先节点。

　　　　所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。

　　　　有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？

　　　　答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点。

　常用的求LCA的算法有：Tarjan/DFS+ST/倍增

　　　　后两个算法都是在线算法，也很相似，时间复杂度在O(logn)~O(nlogn)之间，我个人认为较难理解。

　　　　有的题目是可以用线段树来做的，但是其代码量很大，时间复杂度也偏高，在O(n)~O(nlogn)之间，优点在于也是简单粗暴。

倍增寻找（ST算法）： 此算法基于动态规划。它本质上属于暴力算法的优化版本，只是把暴力算法的一次只跳一步变为了一次跳 2^k 步。算法使用数组 fa[i][j] 表示结点 i 的第 2^j个父亲，则有递推式

fa[i][j]=fa[fa[i][j−1]][j−1]

即:结点 i 的第 2 ^j 个父亲是结点 i ii 的第 2^j-1个父亲的第 2^j-1 个父亲。

算法对于每一个询问 (u,v)，首先将 u 和 v 调整到同一个深度，然后同时向上跳，第一个一样的就是它们的 LCA 。

实现过程： 1.预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u] 2.init()求出树上每个节点u的2^i祖先p[u][i] 3.求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将两个节点同时上移，查询最近公共祖先。

oid dfs(int u) {
    for(int i=head[u]; i!=-1; i=edge[i].next) {
        int to=edge[i].to;
        if(to==p[u][0])continue;
        d[to]=d[u]+1;
        dist[to]=dist[u]+edge[i].w;
        p[to][0]=u;   //p[i][0]存i的父节点
        dfs(to);
    }
}
void init()//i的2^j祖先就是i的（2^(j-1))祖先的2^(j-1)祖先
{
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i<=n; i++)
            p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b) {
    if(d[a]>d[b])swap(a,b); //b在下面
    int f=d[b]-d[a];              //f是高度差
    for(int i=0; (1<<i)<=f; i++)
        //(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
        if((1<<i)&f)b=p[b][i];     //比如f=5，二进制就是101,所以首先移动2^0祖先，然后再移动2^2祖先
    if(a!=b) {
        for(int i=(int)log2(N); i>=0; i--)
            if(p[a][i]!=p[b][i])            //从最大祖先开始，判断a,b祖先，是否相同
                a=p[a][i], b=p[b][i];     //如不相同，a b同时向上移动2^j
        a=p[a][0];          //这时a的father就是LCA
    }
    return a;
}

Tarjan算法（离线算法）: 离线算法，是指首先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解决LCA问题的离线算法，它结合了深度优先遍历和并查集，整个算法为线性处理时间。

在这里插入图片描述

该算法的思想为，对于任意一个结点 r ，处于 r r的不同子树上的两个结点 u ,v ，一定有 LCA(u,v)=r 。这个结论非常显然。首先， r 是 u ,v 的共同祖先；其次，任何深度大于 r 的结点都只会至多存在于 r 的一棵子树中，不可能是既是 u 的祖先又是 v 的祖先，因而 r 是 u , v 的最近公共祖先。

因此，我们可以暂时忽略询问中 u 和 v 的具体位置，而只是关心它们是否在某结点的不同子树中。我们使用并查集存储不同的子树，对于不在同一个并查集中的两个结点，它们的 LCA 即为这两个并查集的根的 LCA 。需注意，并查集是动态变化的，因为子树的划分有多种，子树也有大小之分。我们应该从下往上、由小到大地将子树一棵棵合并，并在同时更新答案。

从具体的实现方式来说，算法按照 dfs 序访问和合并结点，当访问到叶子结点 u 时，对于询问 LCA ( u , v ) ，如果 vv 已经被访问过，则用 v 所在并查集的根的祖先更新 LCA ( u , v ) ，然后一边回溯一边合并一边更新。先不着急给出代码，我们使用一开始给出的那张图作为例子，假设我们要询问 (1,2) ， (2,5) ，(7,8) ， (6,14) ， (10,15) 。算法首先遍历 1 → 2 → 5 ，一路上设置 root [ u ] = u 。当发现到叶子了，看询问，发现有一个 (5,2) ，则更新答案 LCA ( 5 , 2 ) = root ( 2 ) = 2 然后回溯，合并 5 和 2 ，更新答案 LCA ( 2 , 5 ) = root ( 5 ) = 2 和 LCA ( 2 , 1 ) = root ( 1 ) = 1

接着是下一棵子树 3 → 6 → 10 3，同样的把 root 一路设过去，到了 10 。看询问，有个 ( 10 , 15 ) ] ，但 15 没被访问过，直接跳过。回溯，合并 10 和 6，发现有个询问(6,14) ，但 14 也没被访问过，同样跳过。

然后是子树 11 → 15 ， root 设过去，发现询问有 (15,10) ，更新答案 LCA ( 15 , 10 ) = root ( 10 ) = 6 。回溯，合并 15 和 11 。然后， 6 的子树都访问完了，合并 6 , 11 ，不需要更新答案，因为 14 仍然没有访问到。往上，再合并 6 , 3 ，也没有更新操作。

接着就是 7 → 12 ，有个 (7,8) 但还没访问，合并。13 ，合并。到了 14 ，终于更新了，答案为 LCA ( 14 , 6 ) = root ( 6 ) = 3 。回溯，合并合并再合并，目前为止， 3的子树和 2 的子树全和 1在同一个并查集里了。

最后是子树 4 → 8 和 9 ，需要更新的就是 LCA ( 8 , 7 ) = root ( 7 ) = 1 。

Tarjan(u)//marge和find为并查集合并函数和查找函数
{
    for each(u,v)    //访问所有u子节点v
    {
        Tarjan(v);        //继续往下遍历
        marge(u,v);    //合并v到u上
        标记v被访问过;
    }
    for each(u,e)    //访问所有和u有询问关系的e
    {
        如果e被访问过;
        u,e的最近公共祖先为find(e);
    }
}

模拟一遍

　　　　假设我们有一组数据 9个节点 8条边联通情况如下：

　　　　1--2，1--3，2--4，2--5，3--6，5--7，5--8，7--9 即下图所示的树

　　　　设我们要查找最近公共祖先的点为9--8，4--6，7--5，5--3；

　　　　设f[]数组为并查集的父亲节点数组，初始化f[i]=i，vis[]数组为是否访问过的数组，初始为0;　