最近公共祖先

ny_123457 · 2025-01-02 20:30:43 · 算法·理论

Part 1.什么是最近公共祖先？

最近公共祖先又称 LCA，是指在一棵树中距离两（或多个）个节点的最近的祖宗节点。
例如在这张图片中节点 a 和节点 b 的最近公共祖先就是节点 c。

Part 2.怎么解决这个问题？

这两个节点都有一个深度，要先把这两个节点中比较深的那个节点跳到那个没那么深的节点的同一深度，在将两个节点一起网上跳，当两个节点第一次重合时这个重合的节点就是这两个节点的最小公共祖先。
在这之前可以使用深度优先搜索计算每个节点的深度。

Part 3.Tarjan

（此内容源自 oi-wiki）
Tarjan 算法是一种离线算法，需要使用并查集记录某个结点的祖先结点。
做法如下：

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

性质:
Tarjan 算法需要初始化并查集，所以预处理的时间复杂度为 O(n)。
朴素的 Tarjan 算法处理所有 m 次询问的时间复杂度为 O(m \alpha(m+n, n) + n)。但是 Tarjan 算法的常数比倍增算法大。存在 O(m + n) 的实现。

Part 1.例题 1

题目描述

给出一棵有 N（编号 1 到 N）个节点的有根树，求出指定节点对的最近公共祖先！

解法

纯模版题，用深度优先搜索先求每个节点的深度再用本文所讲的第一种解法直接进行求解即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int Max_n=5e5+10;
int n,m,q,s;
int d[Max_n],anc[Max_n][25],dis[Max_n];
bool tou[Max_n];
vector<int>G[Max_n];
void cuntu(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs(int u,int fa){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa)continue;
        d[v]=d[u]+1;
        anc[v][0]=u;
        dfs(v,u);
    }
}
void init(){
    for(int j=1;j<=log2(n);j++){
        for(int i=1;i<=n;i++){
            anc[i][j]=anc[anc[i][j-1]][j-1];
        }
    }
}
int LCA(int u,int v){
    if(d[u]<d[v])swap(u,v);
    for(int i=log2(n);i>=0;i--){
        if(d[anc[u][i]]>=d[v]){
            u=anc[u][i];
        }
    }
    if(u==v)return u;
    for(int i=log2(n);i>=0;i--){
        if(anc[u][i]!=anc[v][i]){
            u=anc[u][i];
            v=anc[v][i];
        }
    }
    return anc[u][0];
}
int main(){
    memset(tou,false,sizeof(tou));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tou[v]=true;
        cuntu(u,v);
    }
    for(int i=1;i<=n;i++){
        if(tou[i]==false){
            d[i]=1;
            dfs(i,0);
            break;
        }
    }
    init();
    scanf("%d",&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        int ans=LCA(u,v);
        printf("%d\n",ans);
    }
    return 0;
}

Part 2.例题 2

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。
每一条道路对车辆都有重量限制，简称限重。
现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

解法

解决本题需要用到重构树，RMQ 和 kruskal 算法的知识。
首先建图上重边选最大边，选取前 n-1 条最大的边构成最大生成树，然后在这棵树上进行操作，求 x 到 y 的路径，如果它们不在一颗树上就输出 -1，否则找 x 和 y 的公共祖先的过程中采用 RMQ 记录路径上边权的最小值。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,k,ans,len,f[maxn][25],depth[maxn],fa[maxn],sum[maxn][25];
bool vis[maxn];
struct node{
    int x,y,z;
}a[maxn];
struct edge{
    int end,last,len,next;
}e[maxn];
int cnt=0;
void add(int a,int b,int c){
    e[++cnt].end=b;
    e[cnt].len=c;
    e[cnt].next=e[a].last;
    e[a].last=cnt;
}
bool cmp(node a,node b){
    return a.z>b.z;
}
int getfather(int u){
    if(u==fa[u])return fa[u];
    return getfather(fa[u]);
}
void dfs(int u,int fa){
    f[u][0]=fa;
    depth[u]=depth[fa]+1;
    vis[u]=true;
    for(int i=1;i<=k;i++){
        f[u][i]=f[f[u][i-1]][i-1];
        sum[u][i]=min(sum[u][i-1],sum[f[u][i-1]][i-1]);
    }
    for(int i=e[u].last;i;i=e[u].next){
        int v=e[i].end;
        int Z=e[i].len;
        if(v!=fa){
            sum[v][0]=Z;
            dfs(v,u);
        }
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    int answer=1e9;
    for(int i=20;i>=0;i--){
        if(depth[f[a][i]]>=depth[b]){
            answer=min(answer,sum[a][i]);
            a=f[a][i];
        }
    }
    if(a==b)return answer;
    for(int i=20;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            answer=min(answer,min(sum[a][i],sum[b][i]));
            a=f[a][i];
            b=f[b][i];
        }
    }
    answer=min(answer,min(sum[a][0],sum[b][0]));
    return answer;
}
void kruskal(){
    int tot=0;
    for(int i=1;i<=m;i++){
        if(tot==n-1)break;
        int fx=getfather(a[i].x);
        int fy=getfather(a[i].y);
        if(fx!=fy){
            fa[fx]=fy;
            tot++;
            add(a[i].x,a[i].y,a[i].z);
            add(a[i].y,a[i].x,a[i].z);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    k=log2(n);
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
    sort(a+1,a+1+m,cmp);
    kruskal();
    for(int i=1;i<=n;i++){
        if(!vis[i])dfs(i,0);
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(getfather(u)!=getfather(v))printf("-1\n");
        else printf("%d\n",LCA(u,v));
    }
    return 0;
}