首先,Tarjan 算法是一个 离线 求 LCA 的算法,与倍增不同。

倍增的做法是 $O(n)$ 预处理,$O(\log n)$回答每一次询问,也就是说可以每输入一次询问就立刻计算输出,是在线算法。

Tarjan 呢,则是先读入完所有的数据,再用一次 dfs 遍历之后全部输出,在读入完之前不能计算出答案,是离线算法。

接下来就是具体的过程。

先假设有这样一棵树。

对于这棵树,我们再假装有这样几组询问:

LCA(4,6),LCA(2,10),LCA(1,6)

首先我们将这几组询问分别存储到对应的点上。假如第 $i$ 组询问需要求 LCA(u,v),为了让从u,v都能够访问到这组询问,我们就以每一个点编号为下标,开一个存放 { 目标点,询问编号 } 的 vector,就像这样.

struct node{//定义部分
    int v,id;
};
vector<node> ask[500010];
...
//对于每组询问u,v
ask[u].push_back((node){v,i});
ask[v].push_back((node){u,i});
...

为了更清晰,在示例图中我们就不记录询问编号。记录完成后如下图:

树2.jpg

这棵询问树完成之后,输入也就完成了,接下来就是离线求 LCA 的环节了。

在这个环节,我们采用 dfs 对其进行一次遍历,但是过程中会穿插来自 并查集 的 get 求祖先操作。初始化即每个点都是自己的父结点。

贴一下 get 操作,后面比较好理解。

int get(int x){
    return fa[x]==x?x:fa[x]=get(fa[x]);
    /*或者写成下面的形式
    if(fa[x]==x)return x;
    else return fa[x]=get(fa[x]);
    */
}

我们把目前经历过但是还没回溯的点标记为红色 R(无实际意义,为了看得更清晰),回溯了的点标记为蓝色 B。是否遍历过就用一个 bool 数组来统计。

以下是具体操作过程,不需要可以跳过。


  • 从根节点 0 出发,先到达 1,发现结点 1 有询问 LCA(1,6),查询发现结点 6 还未遍历,忽略

树3.jpg


  • 从1 出发,到达 2,记录发现结点 2 有询问 LCA(2,10),查询结点 10 还未遍历,忽略。
  • 2 没有子节点了,标记 2 已经访问,回溯到父节点 1记录 fa[2]=1

树4.jpg


  • 从 1 出发,到达 3,记录 fa[3]=1,结点 3 没有询问,继续遍历。

树5.jpg


  • 从 3 出发,分别到达 4,5,结点 4 的询问点没有出现,忽略并回溯;结点 5 没有询问,回溯。记录 fa[4]=fa[5]=3

树6.jpg


  • 从 3 出发,到达 6,记录 fa[6]=3,分别处理结点 6 的两个询问。
  • 对于 LCA(6,4),只需要记录结点 4 的祖先(通过 get),fa[4]=3->fa[3]=3->停止,所以 LCA(6,4) 的答案即为 3,记录在对应答案编号下。
  • 对于 LCA(6,1),同样求结点 1 的祖先,因为 1 还没有回溯,所以fa[1]=1->停止,记录 1 到 LCA(6,1) 下。
  • 结点 6,3,1 回溯,记录 fa[6]=3,fa[3]=1,fa[1]=0,回溯到结点 0.
  • 从 0 出发,遍历结点 7,遍历结点 8,结点 8回溯,记录 fa[8]=7......
  • 其余同理。

好了,下拉到这里就可以了

下面是全过程展示,黄边为已经确定父子结点关系的边。

全过程.gif


相信你已经理解了为什么要把一个询问分成两次记录下来,因为这两次里面虽然只会有一次有效,但是我们不能知道哪一次是有效的,所以就都记录下来,方便判断。

至于原理...首先我们在 LCA(u,v) 的询问中,答案肯定是 $v$ 的祖先,而深度最小的那个,即 $v$ 的祖先中第一个还没有回溯的结点 $f$。$u$ 一定是由f往下递归得到的。可以多看几次 GIF 演示来想想是为什么。


最近公共祖先(模板题)

参考代码如下:

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int to,next;
}e[1000010];
int head[1000010],cnt;
int fa[500010];
bool vis[500010];
int ans[500010];
struct node
{
    int v,id;
};
vector<node> ask[500010];
void add(int u,int v)
{
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void dfs(int u,int f)
{
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=f)dfs(e[i].to,u),fa[e[i].to]=u;
    int len=ask[u].size();
    for(int i=0;i<len;i++)
        if(vis[ask[u][i].v])ans[ask[u][i].id]=get(ask[u][i].v);
    vis[u]=1;
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=500000;i++)
        fa[i]=i;
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        ask[u].push_back((node){v,i});
        ask[v].push_back((node){u,i});
    }
    dfs(s,0);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}
最后修改:2021 年 09 月 02 日
如果觉得我的文章对你有用,请随意赞赏