最近公共祖先(LCA)

2017-09-06

好东西啊,今天终于会了qwq......(左右的dalao都会qaq)

吐槽:有dalao在旁边装萌新.....就我一条咸鱼

LCA主要是有3中方式:Tarjan,倍增,树链刨分

今天我学的是前两种;

说倍增:倍增一共有两种方法,(预处理),就是预处理是可以bfs队列或者dfs直接建立

预处理一共有两种:先说dfs,利用它可以求出dfs序,一棵树的dfs序可以保证同一颗子树里每一个序号都是连续的

先不说这个序的问题，预处理每一个点的深度,然后根据深度决定可以跳过多少次。预处理就像st表一样,每一次以一半增加当前一半的管理范围

但是dfs多次调用函数,可能会导致栈溢出,莫名re...比如我现在弄一个链...10w个点..爆炸)_一般出题人应该不会这样

现在说bfs,它利用队列的思想,把每次和当前所到的点所连的点全部加进队列里,这样保证每一层有相同的bfs序...

把所连边的深度赋成当前点深度+1...这样做出来的和dfs相同...

void dfs(int x){
    vis[x]=1;
    for(int i=f[x];i;i=b[i].nex){
        int v=b[i].to;
        if(!vis[v]){
            fa[v][0]=x;deep[v]=deep[x]+1;
        for(int j=1;j<=20;j++){
            if(!fa[fa[v][j-1]][j-1])break;
            fa[v][j]=fa[fa[v][j-1]][j-1];}
            dfs(v);
        }
    }
}

dfs(预处理)

void bfs(){
    q.push(S);deep[S]=1;vis[S]=1;
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int i=f[v];i;i=b[i].nex){
            int k=b[i].to;
            if(!vis[k]){
                vis[k]=1;
                q.push(k);
                deep[k]=deep[v]+1;
                fa[k][0]=v;
                for(int j=1;j<=22;j++){
                if(!fa[k][j-1])break;
                fa[k][j]=fa[fa[k][j-1]][j-1];}
            }
        }
    }
}

bfs(队列预处理)

我再说一下倍增的实现吐槽,就是我们不知道跳多少步才可以到相应的深度,但是我们不妨设跳k步才能到同一深度....

那么我们从最高枚举2ⁱ...(i<=log₂N)然后log₂N次以后就会把k拆成0;然后他们就在同一深度...

到了同一深度,就可能互相看到对方了......不妨我们还设k步他们才能真正相见..

我们还是从最大的i,i=log₂N开始枚举,继续拆分k,每拆一位就是往上跳2ⁱ。。但是如果相同,就说明k已经小于2ⁱ这时已经不能跳2ⁱ了

所以,我们不能跳了,只能让i-1然后看能不能再跳,知道i=0是最后一次pd,他的再跳1层就是两个点的LCA ..

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
int read(){
    int an=0,f=1;char ch=getchar();
    while(!('0'<=ch&&ch<='9')){if(ch=='-')f=-f;ch=getchar();}
    while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
    return an*f;
}
int x,y,cnt,z,n,m,S;
queue<int>q;
struct saber{
int to,nex;
}b[1000000+999];
int f[500000+999],deep[500000+999];
long long ans;
bool vis[500000+999];
int fa[500000+999][25];
void add(int x,int y){
    cnt++;
    b[cnt].to=y;
    b[cnt].nex=f[x];
    f[x]=cnt;
}
void bfs(){
    q.push(S);deep[S]=1;vis[S]=1;
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int i=f[v];i;i=b[i].nex){
            int k=b[i].to;
            if(!vis[k]){
                vis[k]=1;
                q.push(k);
                deep[k]=deep[v]+1;
                fa[k][0]=v;
                for(int j=1;j<=22;j++){
                if(!fa[k][j-1])break;
                fa[k][j]=fa[fa[k][j-1]][j-1];}
            }
        }
    }
}
int lca(int u,int v){
    if(deep[u]>deep[v])swap(u,v);
    for(int i=20;i>=0;i--)
        if(deep[fa[v][i]]>=deep[u])v=fa[v][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void LCA(int x,int y){
    int p1,p2,p3,t;
    p1=lca(x,y);
    printf("%d
",p1);
}
int main(){
    n=read();m=read();S=read();
    for(int i=1;i<n;i++){
        x=read();y=read();
        add(x,y);add(y,x);
    }
    bfs();
    for(int i=1;i<=m;i++){
        x=read();y=read();
        LCA(x,y);
    }
    return 0;
}

bfs(LCA)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read(){
    int an=0,f=1;
    char ch=getchar();
    while(!('0'<=ch&&ch<='9')){if(ch=='-')f=-f;ch=getchar();}
    while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
    return f*an;
}
const int maxn=500000+999;
int n,m,s,cnt;
int f[maxn],fa[maxn][25],deep[maxn];
bool vis[maxn];
int x,y;
struct saber{
int nex,to;
}b[maxn*2];
void add(int x,int y){
    cnt++;
    b[cnt].nex=f[x];
    b[cnt].to=y;
    f[x]=cnt;}
void dfs(int x){
    vis[x]=1;
    for(int i=f[x];i;i=b[i].nex){
        int v=b[i].to;
        if(!vis[v]){
            fa[v][0]=x;deep[v]=deep[x]+1;
        for(int j=1;j<=20;j++){
            if(!fa[fa[v][j-1]][j-1])break;
            fa[v][j]=fa[fa[v][j-1]][j-1];}
            dfs(v);
        }
    }
}
int lca(int u,int v){
    if(deep[u]>deep[v])swap(u,v);
    for(int i=20;i>=0;i--)
        if(deep[fa[v][i]]>=deep[u])v=fa[v][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    if(u==v)return u;
    return fa[u][0];
}
void Lca(int x,int y){
    int ans=lca(x,y);
    printf("%d
",ans);
}
int main(){
    n=read();m=read();s=read();
    for(int i=1;i<n;i++){
        x=read();y=read();
        add(x,y);add(y,x);}
    deep[s]=1;
    dfs(s);
    for(int i=1;i<=m;i++){
        x=read();y=read();
        Lca(x,y);}
    return 0;
}

dfs(LCA)

by:s_a_b_e_r

应该w同学会在另一篇博客讲Tarjan.....

2017-09-07

树链剖分就是把树切成链,维护链的sum,max,min等...树链剖分求LCA就是看链,连线段树都不用

现在我们假设有一个LCA点C,点A,B;

那么C一定满足在A的链跳k1次,B跳k2次后两个点在同一条链上.这是A,B中深度小的就是点C..

↑不信可以画图啊poi