LCA-Tarjan 算法

LCA 主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径，且你的父亲也是你的祖先，而 LCA 还可以将自己视为祖先节点。

性质：求 B、C 两点间的距离，设 A 点为 B、C 两点的最近公共祖先，D 为任意一点，则有 |BC| = |BD| + |CD| - 2*|AD|。

常用的求LCA的算法有：Tarjan/DFS+ST/倍增，下面介绍离线的 Tarjan 算法：

顾名思义，就是在一次遍历中把所有询问一次性解决，所以其时间复杂度是O(n+q)。

Tarjan 算法基本思路：

1.任选一个点为根节点，从根节点开始。

2.遍历该点 u 所有子节点 v，并标记这些子节点 v 已被访问过。

3.若是 v 还有子节点，返回 2，否则下一步。

4.合并 v 到 u 上。

5.寻找与当前点 u 有询问关系的点 v。

6.若是 v 已经被访问过了，则可以确认 u 和 v 的最近公共祖先为 v 被合并到的祖先节点 a。

遍历的话需要用到dfs来遍历，至于合并，最优化的方式就是利用并查集来合并两个节点。

伪代码：

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

---

经常遇到的几个问题：

1、带权边：可以根据上述性质 |BC| = |BD| + |CD| - 2*|AD|，来解决求带全边的问题。

2、无向图：在访问所有和 u 有询问关系的 e 时，将最终的结果（距离或者最近公共祖先）赋值给该边的反向边，如下