最近公共祖先 LCA

zifuneko · 2024-06-16 17:24:18 · 算法·理论

\text{LCA}

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。为了方便，我们记某点集 S=\{v_1,v_2,\ldots,v_n\} 的最近公共祖先为 \text{LCA}(v_1,v_2,\ldots,v_n) 或 \text{LCA}(S)。

暴力标记法

过程

可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 LCA。或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。

性质

朴素算法预处理时需要 dfs 整棵树，时间复杂度为 O(n)，单次查询时间复杂度为 \Theta(n)。如果树满足随机性质，则时间复杂度与这种随机树的期望高度有关。

// x:now(现在所在的点), f:father(父节点), to(即将前往的点)
void dfs(int x, int f)
{
    for(int i=0; i<t[x].size(); i++)
    {
        int to = t[x][i];
        if(to != f)
        {
            fa[to] = x;
            dfs(to, x);
        }
    }
}

int lca(int a, int b)
{
    memset(vis, 0, sizeof(vis));
    while(a!=0)
    {
        vis[a] = 1;
        a = fa[a];
    }
    while(vis[b] == 0) b = fa[b];
    return b;
}

暴力上跳法

拉齐 a 与 b 深度;

void dfs(int x, int f, int depth)
{
    dep[x] = depth;
    for(int i=0; i<t[x].size(); i++)
    {
        int to = t[x][i];
        if(to != f)
        {
            fa[to] = x;
            dfs(to, x, depth+1);
        }
    }
}

int up(int a, int h)
{
    for(int i=1; i<=h; i++) a = fa[a];
    return a;
}

int lca(int a, int b)
{
    if(dep[a] > dep[b]) a = up(a, dep[a]-dep[b]);
    else b = up(b, dep[b]-dep[a]);
    while(a != b)
    {
        a = fa[a];
        b = fa[b];
    }
    return a;
}

倍增法

void dfs(int x, int f, int depth)
{
    dep[x] = depth;
    for(int i=1; i <= log2(depth); i++)
        fa[x][i] = fa[fa[x][i-1]][i-1];

    for(int i=0; i<t[x].size(); i++)
    {
        int to = t[x][i];
        if(to != f)
        {
            fa[to][0] = x;
            dfs(to, x, depth+1);
        }
    }
}

int up(int a, int h)
{
    int i=0;
    while(h)
    {
        if(h & 1) a = fa[a][i];
        h >>= 1;
        i++;
    }
    return a;
}

int lca(int a, int b)
{
    if(dep[a] > dep[b]) a = up(a, dep[a]-dep[b]);
    else b = up(b, dep[b]-dep[a]);
    if(a == b) return a;
    for(int i=log2(dep[a]); i >= 0; i--)
    {
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

时间复杂度

预处理：

\text{depth}$： $O(n)
fa[i][j]$： $O(n \log n)

询问： O(m \log n)

Tarjan算法

过程 Tarjan 算法是一种离线算法，需要使用并查集记录某个结点的祖先结点。做法如下：

首先接受输入边（邻接链表）、查询边（存储在另一个邻接链表内）。查询边其实是虚拟加上去的边，为了方便，每次输入查询边的时候，将这个边及其反向边都加入到 queryEdge 数组里。
然后对其进行一次 DFS 遍历，同时使用 visited 数组进行记录某个结点是否被访问过、parent 记录当前结点的父亲结点。
其中涉及到了回溯思想，我们每次遍历到某个结点的时候，认为这个结点的根结点就是它本身。让以这个结点为根节点的 DFS 全部遍历完毕了以后，再将这个结点的根节点设置为这个结点的父一级结点。
回溯的时候，如果以该节点为起点，queryEdge 查询边的另一个结点也恰好访问过了，则直接更新查询边的 LCA 结果。
最后输出结果。

// Tarjan算法
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500005;

// 存储询问的结构体
struct Node{
    int a,b,ans;
}xw[MAXN * 2];

// gl[i]存储所有a=i的询问
vector<int> gl[MAXN];
int n,m,s;
vector<int> mp[MAXN];

int fa[MAXN];

/// 并查集套件
int xfind(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = xfind(fa[x]);
}

// 设定x的fa为y
void xmerge(int x, int y)
{
    int fx = xfind(x);
    int fy = xfind(y);
    fa[fx] = fy;
}

void init(int n) {for(int i=1; i<=n; i++) fa[i] = i;}

bool vis[MAXN];
void tarjan(int x, int f) // dfs f代表父节点编号
{
    vis[x] = 1;
    for(int i=0;i<mp[x].size();i++)
    {
        int to = mp[x][i];
        if(to != f)
        {
            tarjan(to, x);
        }
    }
    // 处理相关询问
    for(int i=0; i<gl[x].size();i++)
    {
        int xb = gl[x][i];
        // xw[xb].a == x;

        /// 关键点
        if(xw[xb].ans == 0 && vis[xw[xb].b])
        {
            xw[xb].ans = xfind(xw[xb].b);
            if(xb % 2 == 0) xw[xb-1].ans = xw[xb].ans;
            else xw[xb+1].ans = xw[xb].ans;
        }
    }
    xmerge(x, f);
}

int main()
{
    cin >> n >> m >> s;
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        cin >> x >> y;
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    int cnt = 1;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;
        xw[cnt].a = a;
        xw[cnt].b = b;
        gl[a].push_back(cnt);
        cnt ++;

        xw[cnt].a = b;
        xw[cnt].b = a;
        gl[b].push_back(cnt);
        cnt ++;
        // a-b询问存在i，b-a询问存在i+1
    }
    init(n);

    tarjan(s,0);
    for(int i=1; i<cnt; i+=2) cout << xw[i].ans << endl;

    return 0;
}

性质

Tarjan 算法需要初始化并查集，所以预处理的时间复杂度为 O(n)。

朴素的 Tarjan 算法处理所有 m 次询问的时间复杂度为 O(m \alpha(m+n, n) + n)。但是 Tarjan 算法的常数比倍增算法大。存在 O(m + n) 的实现。

\text{LCA} 的性质

性质内容全部来自于 https://oi-wiki.org/graph/lca/

如果 u 不为 v 的祖先并且 v 不为 u 的祖先，那么 u,v 分别处于 \text{LCA}(u,v) 的两棵不同子树中；
前序遍历中，\text{LCA}(S) 出现在所有 S 中元素之前，后序遍历中 \text{LCA}(S) 则出现在所有 S 中元素之后；
两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 \text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))；
两点的最近公共祖先必定处在树上两点间的最短路上；

\text{DFS} 序与欧拉序

\text{DFS} 序

进去记录，出去记录。

可以把树数据结构转换为线性数据结构，从而可以把基于线性数据的算法间接用于处理树上的问题。堪称降维打击。
相同编号之间的节点编号为以此编号为根节点的子树上的所有节点编号。
如果一个节点的编号连续相同，则此节点为叶节点。
树的 dfs 序的长度是 2N（N 表示节点的数量）
两个相同节点围成的是他的子树。

欧拉序

进入节点时记录，每次遍历完一个子节点时，返回到此节点记录，得到的 2\times n-1 长的序列。

节点 x 第一次出现与最后一次出现的位置之间的节点均为 x 的子节点；
任意两个节点的 LCA 是欧拉序中两节点第一次出现位置中深度最小的节点，两个第一次出现的位置之间一定有它们的 LCA，而且，这个 LCA 一定是这个区间最小的值。