LCA问题总结

@Llf  April 10, 2018

概述

最近公共祖先(LCA)问题指的是在一棵树中,求出任意两个点的最近的公共祖先。如在下图中:

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;
}

未完待续


添加新评论