在讲解之前，我们先来看一道模板题：Luogu P3379 最近公共祖先（LCA)
What is LCA
LCA,即最近公共祖先。什么意思呢，我们举个例子：
将就着看吧qwq
这棵树中，0为根节点。若规定\(LCA(x,y)\)为\(x,y\)的最近公共祖先，则\(LCA(5,6)=2;LCA(4,3)=1;LCA(5,3)=0\)。还有很多，这里不一一列举了。
最近公共祖先，顾名思义，是指两个节点最近的公共祖先。求解它有很多种方法，包括但不限于暴力，倍增，RMQ。这里主要介绍Tarjan算法。
Tarjan
- Tarjan算法是一种离线算法，跑一遍就能将所有需求的LCA计算完，因此效率比较高。
- Tarjan实现应用了DFS搜索树+并查集 （
相信来看的都懂吧）
算法步骤：
1.从根节点开始搜索树，如果搜到的点还有子节点则继续搜（DFS)
2.若搜到的节点没有子节点或子节点已经搜索过了，将父节点和子节点合并（并查集）
3.查找与当前节点\(now\)有询问关系的节点\(q_i\),若\(q_i\)已经回溯过则
\(LCA(now,q_i)=find(q_i)\) (\(find(q_i)\)指并查集操作，查找\(q_i\)的父节点)
需要注意，在STEP3中，\(q_i\)必须是已经回溯过而不是搜过，只有回溯过才有merge操作。（如果不理解可以先看下文模拟）
整个算法的过程非常巧妙，笔者水平有限，无法给出具体证明（ 我太菜了ww），这里带着大家模拟一遍Tarjan流程吧，模拟完相信大家对Tarjan的理解就会更加深刻啦
模拟样例
我们还是模拟最先给出的那棵树：
为了简化题意，我们假设需求\(LCA(5,6)\)以及\(LCA(5,4)\)
显然，从0根节点开始DFS，先搜2，2还有子节点，先搜5，发现没有子节点。则merge（2，5）
此时，查找与5有询问关系的点：
- 关系1：6号点。显然没有回溯过，不管
- 关系2：4号点。显然也没有回溯过，不管
此时回溯，返回2号，搜索6号。发现6没有子节点。则merge（2，6）
此时，查找与6有询问关系的点：
- 关系1：5号点。已经回溯过，则\(LCA(5,6)=find(6)=2\)
此时回溯，返回0号，并且merge(2,0),搜索1号，1号有子节点，先搜4，merge(1,4)。
查找与4号有询问关系的点：
- 关系1：5号点。已经回溯过，则\(LCA(4,5)=find(5)=0\)
显然还会继续搜索下去，和上边同理，相信大家对Tarjan算法已经有了深刻的理解，这里不继续模拟了。
具体实现
通过Tarjan，我们可以求出所有需要求的LCA,但是如何存储答案，去重，输出呢？
我们可以用vector存树（注意一定是双向边），另开一个vector存储询问顺序实现按顺输出+去重。当然去重也可以用map，只不过浪费空间。
我们来看一下Tarjan模板：
void tarjan(int now)
{
vis[now] = 1; //标记已访问
for(int i=0;i<v[now].size();i++) //这里使用了vector存树
{
if(!vis[v[now][i]]) //如果子节点没访问过
{
tarjan(v[now][i]); //dfs继续搜
fa[v[now][i]] = now; //merge操作
}
}
for(int i=0;i<q[now].size();i++) //查找与now有询问关系的点
{
int p =find(q[now][i]);
if(vis[q[now][i]] == 2) //如果询问的点回溯过
{
ans[id[now][i]] = p; //id存答案编号，即按序输出
}
}
vis[now] = 2;//所有操作完毕后标记now已回溯
}
至于刚开始给出的模板题，由于已经给出了Tarjan板子，其余部分自己实现一下吧！
标签：Tarjan,LCA,merge,算法,回溯,节点 From： https://www.cnblogs.com/SXqwq/p/17500828.html