【luogu3379】【poj1130】LCA最近公共祖先【模板】[LCA]

模板

也是看着学长的模板改的.....

讲解都是黄学长的课件里的放上来方便我自己看吧他讲的太好辽

倍增

首先对于每个结点先进行DFS 预处理出它的深度，再记录下它们往父亲方向走2⁰ 2¹...2^k步所到达的结点在这里2^k大于整棵树的最大深度

预处理完后，需要查询两个点u和v的LCA的时候，先将u和v中深度较大的一个利用先前处理出的数组走到和另一个结点相同的深度

接下来从k开始往下枚举，如果u和v如果往上走2ⁱ后不相同，那么就将它们一起往上走这么多步。
结束后如果u和v仍然不相等，再往上走一步。最后的顶点就是它们的LCA

倍增算法预处理的复杂度预处理是O(nlogn)，每次查询都是O(logn)
我们还可以动态地给树增加一些叶子结点
在预处理的时候还可以顺便记录下这段路径的权值最大值最小值或者权值和之类的信息，这样就可以在O(logn)的时间内求出树上两点间路径权值的最大值、最小值还有权值和

upd 2019.8.16 突然喜欢在dfs完之后再倍增记录

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=500000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,root;
int dep[N],f[N][25];

template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]};head[u]=tot;
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs(e[i].v,u);
    }
}
    
void doubling(){
    for(rg int i=1;i<=20;++i)
        for(int j=1;j<=n;++j)
        if(dep[j]>=1<<i) f[j][i]=f[f[j][i-1]][i-1];
}

int LCA(int a,int b){
    if(dep[a]>dep[b]) swap(a,b);
    for(rg int i=20;i>=0;--i){
        if(dep[f[b][i]]<dep[a]) continue;
        b=f[b][i];
    }
    if(b==a) return a;
    for(rg int i=20;i>=0;--i){
        if(f[a][i]==f[b][i]) continue;
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}

int main(){
    memset(dep,0,sizeof(dep));dep[0]=-1;
    rd(n),rd(m),rd(root);
    for(rg int i=1;i<n;++i){
        int u,v;rd(u),rd(v);
        add(u,v),add(v,u);
    }
    dfs(root,0);
    doubling();
    for(rg int i=1;i<=m;++i){
        int a,b;rd(a),rd(b);
        printf("%d
",LCA(a,b));
    }
    return 0;
}//lxyyyy

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=500000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,root;
int dep[N],f[N][25];

template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]};head[u]=tot;
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(rg int i=1;i<=20;++i){
        if(dep[u]<(1<<i)) break;
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs(e[i].v,u);
    }
}

int LCA(int a,int b){
    if(dep[a]>dep[b]) swap(a,b);
    for(rg int i=20;i>=0;--i){
        if(dep[f[b][i]]<dep[a]) continue;
        b=f[b][i];
    }
    if(b==a) return a;
    for(rg int i=20;i>=0;--i){
        if(f[a][i]==f[b][i]) continue;
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}

int main(){
    memset(dep,0,sizeof(dep));dep[0]=-1;
    memset(f,0,sizeof(f));
    rd(n),rd(m),rd(root);
    for(rg int i=1;i<n;++i){
        int u,v;rd(u),rd(v);
        add(u,v),add(v,u);
    }
    dfs(root,0);
    for(rg int i=1;i<=m;++i){
        int a,b;rd(a),rd(b);
        printf("%d
",LCA(a,b));
    }
    return 0;
}//lxyyyy

以前的

RMQ

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#define N 100010
#define M 21
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
int n;
int f[N][M];
int a[N];
void RMQ()
{    Run(j,1,n)
    f[j][0]=a[j];
    Run(i,1,20)
    Run(j,1,n)
    {     if (j+(1<<i)-1>n) break;
        f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);
    }
}
int main()
{    freopen("ex.in","r",stdin);
    freopen("ex.out","w",stdout);
    scanf("%d",&n);
    Run(i,1,n){
        scanf("%d",&a[i]);
    }
    RMQ();
    int q; 
    scanf("%d",&q);
    Run(i,1,q){
        int l,r;
        scanf("%d%d",&l,&r);
        int x=floor(log(r-l+1)/log(2));
        int ans=max(f[l][x],f[r-(1<<x)+1][x]);
        cout<<ans<<endl;
    }
    return 0;
}//by tkys_Aus tin;

RMQ

tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=500000+5,M=500000+5,INF=1e9+7,inf=0x3f3f3f3f;
const double eps=1e-4;
int n,m,rt,ans[M];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int head2[N],tot2=0;
struct edge2{int v,nxt,id;}q[M<<1];
void add2(int u,int v,int id){
    q[++tot2]=(edge2){v,head2[u],id},head2[u]=tot2;
}

bool vis[N];int f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void dfs(int u,int ff){
    f[u]=u,vis[u]=1;
    for(int i=head2[u];i;i=q[i].nxt)
    if(vis[q[i].v]) ans[q[i].id]=find(q[i].v);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].v;
        if(v==ff) continue;
        dfs(v,u);f[v]=u;
    }
}

int main(){
//    freopen("in.txt","r",stdin);
    rd(n),rd(m),rd(rt);
    for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v),add(v,u);
    for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add2(u,v,i),add2(v,u,i);
    dfs(rt,0);
    for(int i=1;i<=m;++i) printf("%d
",ans[i]);
    return 0;
}

【luogu3379】【poj1130】LCA最近公共祖先 【模板】[LCA]

倍增

RMQ

tarjan

【luogu3379】【poj1130】LCA最近公共祖先【模板】[LCA]