概述

最近公共祖先（LCA）问题指的是在一棵树中，求出任意两个点的最近的公共祖先。如在下图中：

2号节点和1号节点的LCA是4,3号和2号的LCA也是4.

求LCA的方法主要有：暴力，倍增，RMQ和Tarjan。

这篇文章以洛谷P3379 【模板】最近公共祖先（LCA）为例。

Tarjan算法

Tarjan算法能够通过dfs将树上节点信息和查询的信息一次性解决，但是无法应对存在修改的情况，所以是一种离线算法。

方法

1. 从根节点开始，遍历每一个它的子节点；
2. 一直递归到叶节点，再从叶节点开始将它和它的父节点运用并查集合并；
3. 又从当前遍历到的节点u开始，遍历每一个和它有询问关系的节点。如果另一个节点v被访问过，那么u和v的LCA就是v的先前通过并查集找到的祖先。

细节与实现

1. 注意记录这个节点是否被访问过，防止重复访问。
2. 输入没有指明哪个是父节点哪个是子节点，所以需要进行双向储存，空间也要随之开两倍。
3. 由于需要遍历子节点，我采用链式前向星的方法进行储存；同样，还需要遍历有查询关系的点，查询关系也需要用一个链式前向星。
4. 这道题中，有多组询问，还要求按照询问的顺序输出，所以解决每个答案的顺序是至关重要的。我起先想了很久怎么解决这个问题，后来才想起链式前向星也是有顺序的。但是由于每一次询问都存了两次，所以更新LCA答案时要将相邻的一对询问都更新，输出时也只能输出一次。
5. 要处理相邻两个询问的LCA，将本次查询到的节点i和i^1节点更新即可。因为[i,i^1]∈[k*2,k*2+1],k∈Z，i^1即为i在同组中另一项，反之也成立。举个例子：

0^1=1,1^1=0 [0,1]
2^1=3,3^1=2 [2,3]

代码及注解

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int to,next;
} edge[1000005];
struct Edge2{
    int to,next,lca;
} ask[1000005];//链式前向星储存
bool vis[500005];
int f[500005];
int head[1000005],hask[1000005];
int n,m,a,b,c,cnte,cnta,root;
inline void addedge(int u,int v)
{
    edge[cnte].to=v;
    edge[cnte].next=head[u];
    head[u]=cnte++;
}
inline void addask(int u,int v)
{
    ask[cnta].to=v;
    ask[cnta].next=hask[u];
    hask[u]=cnta++;
}
int find(int x)
{
    if (f[x]==x) return f[x];
    f[x]=find(f[x]);
    return f[x];
}
void merge(int x,int y)
{
    if (find(x)!=find(y)) f[find(x)]=find(y);
}
void tarjan(int u)
{
    vis[u]=true;//记录已经访问
    for (int i=head[u];i!=-1;i=edge[i].next) 
    if (!vis[edge[i].to])
    {
        tarjan(edge[i].to);//继续向下遍历
        merge(edge[i].to,u);//合并
    }
    for (int i=hask[u];i!=-1;i=ask[i].next)
    if (vis[ask[i].to]) ask[i].lca=ask[i^1].lca=find(ask[i].to);//i^1的含义是(0,1),(1,2)这些组的另一项
}
int main()
{
    memset(vis,false,sizeof(vis));
    memset(head,-1,sizeof(head));
    memset(hask,-1,sizeof(hask));
    scanf("%d%d%d",&n,&m,&root);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        addask(a,b);
        addask(b,a);
    }
    tarjan(root);
    for (int i=0;i<m*2;i+=2) printf("%d\n",ask[i].lca);//因为加入两次，而相邻两次的lca又相同
    return 0;
}

未完待续

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/lca.html