离线快速LCA(最近公共祖先) Tarjan算法
前言
对于 OIer 来说,LCA 一直是处理树上问题的好帮手,无论是倍增还是树剖都有着优秀的 \(\log n\) 的复杂度。不过由于我们(数据规模)的上进,需要更快速求 LCA,于是就有了……
反正之前打死我都不相信这玩意能离线,还能 O(1)
算法思路
首先来一棵树:
![](https://cdn.luogu.com.cn/upload/image_hosting/xqqvmklh.png)
我们然后我们将要求 LCA 的点对之间加上一条虚边:
如图,我们将对求点 (7,5)、(8,9)、(11,3) 的 LCA。
一开始每个节点属于一个并查集。
接下来我们通过原树边 DFS 遍历每一个节点,在该节点 \(u\) 的子树遍历完成之后,通过该节点 \(u\) 的虚边遍历与之求 LCA 的节点 \(v\)。
此时如果 \(v\) 已经通过原树边遍历过,那么他们的 LCA 等于 \(v\) 节点的并查集根节点。
反之则不进行任何操作。
然后节点 \(u\) 的并查集祖先设为 \(u\) 在原树上的父亲。
解释一下原理:
当前 \(u\) 子树已经遍历过以后,子树 \(u\) 的并查集根节点的子树 \(t\) 一定还没有遍历完,也就是说此时还在遍历 \(t\) 的子树,如果与节点 \(v\) 要求 LCA 的节点是 \(u\),且此时 \(v\) 通过虚边遍历到了 \(u\)。
不难发现 \((u,v)\) 的公共祖先肯定有 \(t\),而 \(u\) 和 \(v\) 又属于节点 \(t\) 不同的分支,所以 \((u,v)\) 的最近公共祖先就是 \(t\)。
这种通过并查集连接祖先求 LCA 的方法十分巧妙。
CODE
inline void dfs(int u)
{
for(ri i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(vis[v]) continue;
dfs(v);
fa[v]=u;//并查集连向父亲
}
for(pair<int,int> i:EL[u])//遍历虚边
{
if(vis[i.F]) Lca[i.S]=frt(i.F);//frt 求该并查集的根
}
vis[u]=1;//遍历标记
}
//i.F 是节点的编号,i.S 是问题的编号
时间复杂度分析
预处理 \(O(n)\),处理完直接使用 \(O(1)\)。
总时间 \(O(n)\),均摊 \(O(1)\)。