tarjan 之 LCA 学习笔记
tarjan算法求LCA可谓是一个极其巧妙的离线算法
其本质是利用 DFS 遍历时产生的 DFS 序 和 并查集 来在线性的时间复杂度内求出所有询问的结果
既然是离线算法，其和在线算法的区别就在与离线算法需要记录下所有查询，对查询进行一定操作来得到更高的效率 ，而这种操做往往是排序之类的
Tarjan求LCA 也是如此
先把所有询问离线下来，将询问的信息存在询问的两个节点上
首先，在树上的两个节点 \(x\) , \(y\) 只可能有两种关系（此处假定y的深度比x深）
1.\(y\) 在 \(x\) 的子树上
2.\(y\) 不在 \(x\) 的子树上
对于第一种关系，我们能很容易看出 \(x\) 就是要求的最近公共祖先
在 DFS 时，从 \(x\) 进入这一棵子树，毫无疑问的会遍历到 \(y\) 并将其打上标记
当回溯到 \(x\) 时若 \(y\) 已经打了标记，显然 \(x\) 就是要求的 LCA
对于第二种关系，我们假设 \(x\) 和 \(y\) 的 LCA 是 \(c\)
当我们从 \(c\) 进入子树后 \(x\) 和 \(y\) 中一定会有一个先被遍历到
在遍历到 \(x\) \(y\) 中的另一个点时，若对方已被标记，则 \(x\) 与 \(y\) 共同所在的这颗子树的根就是 LCA
所以，现在问题来了，我们怎么求 \(c\) 点呢？
Tarjan 发现，这个问题可以用并查集来解决
在 DFS 回溯的过程中 将一个节点在的父节点记为他在并查集中的父节点
随着逐级的回溯，\(y\) 点在并查集中的父节点会逐步上升直到 根节点
而当其在并查集中的父节点 上升到 \(c\) ，也就是 在 \(c\) 点遍历完了 \(y\) 所在的 \(c\) 点的子树后，还会 继续遍历 \(c\) 点的其他儿子及其子树，也就会遍历到 \(x\) 点 当遍历到 \(x\) 时，再查找 \(x\) 存储的查询 找到与 \(y\) 点有关的查询时，会发现 \(y\) 点被访问过
那么这个查询的答案也就是 LCA 就是 \(y\) 点在并查集中的父节点
好了，问题就这样解决了。。。吗？
当 \(x\) 查找查询时若 \(y\) 点还没被访问，也就是 \(x\) 点比 \(y\) 点先被访问怎么办？
没事，因为这个查询再 \(x\) 和 \(y\) 上都存了一遍，所以 当遍历到 \(y\) 时还是能得到查询的答案（你可以理解为将 \(x\) 和 \(y\) 对应的点互换了（相对之前的情况） ）
还有复杂度的分析
首先，每个节点都被遍历了一遍 复杂度 O(n)
而每个查询 被其查找的两个节点 各遍历一次再加上并查集 复杂度 \(O(m*\alpha (m+n,n) + n)\)
所以总复杂度 \(O(m*\alpha (m+n,n) + n)\) 约等于 \(O(m + n)\)
这下真正结束了
上代码！
#include<bits/stdc++.h>
using namespace std;
struct node
{
vector<int> son;
//int fa;
bool vis;
vector<pair<int,int > > query;//存与这个点有关的查询 first 是 查找的另一个点 second 是查询的编号
};
node nodes[600000];
int fa[600000];
int ans[600000];//得出查询的答案
int n,m,r;//r==root
int fnd(int x)//路径压缩并查集
{
if(fa[x]==x)
{
return x;
}
fa[x]=fnd(fa[x]);
return fa[x];
}
void tarbuild(int now_)
{
nodes[now_].vis=1;//标记这个节点已被访问过
int to_;
for(int yy=0;yy<nodes[now_].son.size();yy++)//遍历所有儿子节点（此时没有管父节点是因为父节点已被访问过）
{
to_=nodes[now_].son[yy];
if(nodes[to_].vis==0)//若此儿子节点没有被访问过
{
tarbuild(to_);//递归
fa[to_]=now_;//回溯
}
}
for(int yy=0;yy<nodes[now_].query.size();yy++)//查找所有查询
{
int num_=nodes[now_].query[yy].second;
int nod=nodes[now_].query[yy].first;
if(nodes[nod].vis)//若被访问过
{
ans[num_]=fnd(nod);//得出查询结果
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>r;
for(int yy=1;yy<=n;yy++)
{
fa[yy]=yy;
}
int a,b;
for(int yy=1;yy<n;yy++)
{
cin>>a>>b;
nodes[a].son.push_back(b);
nodes[b].son.push_back(a);
}
for(int yy=1;yy<=m;yy++)
{
cin>>a>>b;
nodes[a].query.push_back({b,yy});//存查寻
nodes[b].query.push_back({a,yy});//两个点都要存一次
}
tarbuild(r);//tarjan
for(int yy=1;yy<=m;yy++)
{
cout<<ans[yy]<<"\n";
}
return 0;
}