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;　

下面开始模拟过程：

　　　　取1为根节点，往下搜索发现有两个儿子2和3；

　　　　先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；

　　　　发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；

　　　　发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；

　　　　

　　　　表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;

　　　　先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其有关系的点；

　　　　发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；

　　　　发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；

　　　　表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找与其有关系的点；

　　　　发现5和7有关系，但是vis[5]=0，所以不操作；

　　　　发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；

　　　　

　　　　表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；

　　　　发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为find(9)=5；

　　　　　　(find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

　　　　发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；

 

　　　　表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；

　　　　

　　　　发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；

　　　　　　(find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

　　　　又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全部搜完了；

　　　　返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；

　　　　发现2没有未被搜完的子节点，寻找与其有关系的点；

　　　　又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；

　　　　

　　　　表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；

　　　　搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；

　　　　此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;

　　　　　　(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

　　　　发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已经被搜完了；

　　　　

　　　　更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；

　　　　发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为find(5)=1；

　　　　　　(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

　　　　发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；

　　　　

　　　　更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。