最近公共祖先(LCA)

突然发现自己连LCA的博客都没写。。。赶忙补起来

关于LCA

理解起来动态LCA及其简单,静态的就难了一些。

写起来静态比动态可能要少1/3。

前置知识:树上倍增(动态)、并查集(静态)

知识重点:LCA如何向上跳(动态),并查集如何使用(静态)

思路

树上倍增

预处理

1.处理深度

2.预处理树每一个节点的父亲、爷爷、4代祖宗、8代祖宗……

因为众所周知2的次方可以组成任意数,于是这样就可以用log的速度向上跳跃。

void dfs(int now,int fa,int level){//处理父亲节点和深度
    father[0][now]=fa;
    depth[now]=level;
    int Size=G[now].size();
    for(vector<int>::iterator i=G[now].begin();i<G[now].end();i++){
        if(*i!=fa)dfs(*i,now,level+1);
    }
    return ;
}
void init(){//由父亲推出爷爷,推出4代祖宗,推出8代祖宗……
    dfs(s,-1,1);
    for(int i=0;i<logg;i++){
        for(int j=1;j<=n;j++){
            if(father[i][j]<0){
                father[i+1][j]=-1;
            }else{
                father[i+1][j]=father[i][father[i][j]];
            }
        }
    }
    return ;
}

LCA

求x,y的LCA

1.将x,y归到同一深度。

2.一起向上跳2^n,n为log(节点数)。如果遇到了那就不跳,跳2^(n-1),如果还是太大,就跳2^(n-2)......,最后必能跳到父亲节点是同一点的两个节点,则只需要输出其父亲即可。

int LCA(int a,int b){
//到达同一深度
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int i=0;i<=logg;i++){
        if((depth[a]-depth[b])>>i&1==1){
            a=father[i][a];
        }
    }
    if(a==b){
        return a;
    }
//一起向上
    for(int i=logg;i>=0;i--){
        if(father[i][a]!=father[i][b]){
            a=father[i][a];
            b=father[i][b];
        }
    }
    return father[0][a];
}

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> G[500005];
int father[30][500005];
int depth[500005];
int n,m,s;
int logg;
void dfs(int now,int fa,int level){
    father[0][now]=fa;
    depth[now]=level;
    int Size=G[now].size();
    for(vector<int>::iterator i=G[now].begin();i<G[now].end();i++){
        if(*i!=fa)dfs(*i,now,level+1);
    }
    return ;
}
void init(){
    dfs(s,-1,1);
    for(int i=0;i<logg;i++){
        for(int j=1;j<=n;j++){
            if(father[i][j]<0){
                father[i+1][j]=-1;
            }else{
                father[i+1][j]=father[i][father[i][j]];
            }
        }
    }
    return ;
}
int LCA(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int i=0;i<=logg;i++){
        if((depth[a]-depth[b])>>i&1==1){
            a=father[i][a];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=logg;i>=0;i--){
        if(father[i][a]!=father[i][b]){
            a=father[i][a];
            b=father[i][b];
        }
    }
    return father[0][a];
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    logg=log2(n)+1;
    int k=n-1;
    for(int i=0;i<k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init();
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

静态LCA

以下图为例
graph.png
若我们要求8和9的LCA,可以同过如下操作:
1.DFS全图,回溯到8的时候,发现9还未回溯。
2.8和7缩为一点
3.8,7,5缩为一点
2.回溯到9的时候将9和5缩为一点,发现8回溯到了,所以8所在并查集的根节点就是LCA(x,y)。

由于我们用的是并查集,并非真正意义上的缩点,所以必有父节点,且我们将x节点直接指向其父节点即可。

大概有人想问为什么似乎LCA(x,y)与x的关系不大,求的只是9的并查集中的根。

因为我们回溯过x之后,就知道x的子树全都被遍历过了,所以y要么在它到根节点的链上,要么在其父节点的其他子树上。

1.若在它到根节点的链上,总归会回溯到y点。

2.若在其它子树上,这也是我们回溯过LCA(x,y)才会到y节点,而此时x已经并为节点LCA(x,y)中的一员了。

而第一种情况也是第二中情况的特殊情况,可以直接用第二种情况的求解方法求解。

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int head[40005];
struct edge{
    int nxt,to,dis;
}edge[80005];
int tot;
int dis[40005];
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    head[u]=tot;
    return ;
}
vector<int> query[40005];
vector<int> query_time[40005];
void add_query(int u,int v,int t){
    query[u].push_back(v);
    query_time[u].push_back(t);
    return ;
}
int fa[40005];
bool vis[40005];
int ans[205];
int find(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void DFS(int x,int f){
    fa[x]=x;
    int nxt;
    for(int i=head[x];i;i=edge[i].nxt){
        nxt=edge[i].to;
        if(nxt==f)continue;
        dis[nxt]=dis[x]+edge[i].dis;
        DFS(nxt,x);
        fa[nxt]=x;
    }
    vis[x]=1;
    int Size=query[x].size();
    for(int i=0;i<Size;i++){
        int id=query_time[x][i];
        int y=query[x][i];
        if(!vis[y])continue;
        int fy=find(y);
        ans[id]=dis[x]+dis[y]-dis[fy]*2;
    }
    return ;
}
int main(){
    cin>>T;
    int u,v,w;
    for(int cas=0;cas<T;cas++){
        cin>>n>>m;
        memset(edge,0,sizeof(edge));
        memset(head,0,sizeof(head));
        for(int i=0;i<n-1;i++){
            cin>>u>>v>>w;
            add_edge(u,v,w);
            add_edge(v,u,w);            
        }
        for(int i=0;i<m;i++){
            cin>>u>>v;
            add_query(u,v,i);
            add_query(v,u,i);
        }
        memset(vis,0,sizeof(vis));
        dis[1]=0;
        DFS(1,-1);
        for(int i=0;i<m;i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/649/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者