LCA详解
LCA，即最近公共祖先，在图论中应用比较广泛。
LCA的定义如下：给定一个有根树，若节点$z$同时是节点$x$和节点$y$的祖先，则称$z$是$x,y$的公共祖先；在$x,y$的所有公共祖先当中深度最大的称为$x,y$的最近公共祖先。下面给出三个最近公共祖先的例子：
显然，从上面的例子可以得出，$LCA(x,y)$即为$x,y$到根节点的路径的交汇点，也是$x$到$y$的路径上深度最小的节点。
求LCA的方法通常有三种：
- 向上标记法
- 树上倍增法
- Tarjan算法
当然，求LCA还有其它方法，例如树剖等，请读者自行了解，本文主要讲解上面提到的三种方法。
P1084
读者可以先尝试解题，实在解不出来再借鉴题解的思路。
。
求LCA的Tarjan算法主体由dfs实现，并用并查集进行优化。对于每个节点，我们增加一个标记：
- 若该节点没有访问过，则初值为0
- 若该节点已访问但还没有回溯，则标记为1
- 若该节点已访问且已回溯，则标记为2
显然，对于当前访问的节点$x$，它到根节点的路径一定都被标记为1。因此对于任意一个与$x$相关的询问，设询问的另一个节点为$y$，则$LCA(x,y)$即为$y$到根节点的路径中第一个，也就是最深的标记为1的节点。
求这个节点的方法可以用并查集优化。当一个节点的标记改为2的同时，将它合并到其父节点的集合当中。显然，此时它的父节点的标记一定为1，并且单独构成一个集合，因为这个父节点还没有进行过回溯操作。
在合并过后，遍历关于当前节点$x$的所有询问，对于任意一个询问，若$y$的标记为2，说明其已经被访问过，并且它的并查集指向的那个节点，也就是$y$到根节点的路径中最深的还没有回溯的节点，一定就是$LCA(x,y)$。
对于询问，我们可以用一个不定长数组存储与每个节点相关的询问，并且每个询问用一个二元组表示，第一维存储该询问的另一个节点，第二维存储该询问输入的次序，以便按顺序输出
这样，Tarjan算法求LCA的步骤就很明了了：
- 从根节点开始进行dfs
- 将当前节点标记为1
- 遍历当前节点的所有出边；若当前边的终点还没有访问过，则访问它，访问过后将该节点合并到当前节点的集合中；
- 遍历与当前节点相关的所有询问；若当前询问的另一个节点的标记为2，则该询问的答案即为另一个节点所在集合的代表元素
- 将当前节点标记为2
思路清晰之后，实现起来不会很难
Tarjan算法代码：
#include
#include
#include
#include
using namespace std;
const int N=6e5;
int n,m,s,tot=0,fa[N],v[N],ans[N],ver[2*N],Next[2*N],head[N];
vector< pair > query[N];
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}//邻接表插入操作
int get(int a)
{
return fa[a]==a?a:fa[a]=get(fa[a]);
}//并查集查找操作
void add_query(int x,int y,int id)
{
query[x].push_back(make_pair(y,id));
query[y].push_back(make_pair(x,id));
}//添加询问
void tarjan(int x)
{
v[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(v[y])
continue;//若访问过则不再访问
tarjan(y);
fa[y]=x;//将子节点合并到自己的集合中
}//遍历所有出边
for(int i=0;i>n>>m>>s;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i
习题：
- 模板题：P3379
- 简单应用题：P3884
声明：本文部分内容参考lyd的蓝书。
2019.5.14 于厦门外国语学校石狮分校