必威体育Betway必威体育官网
当前位置:首页 > IT技术

【学习笔记】LCA

时间:2019-10-10 14:45:45来源:IT技术作者:seo实验室小编阅读:51次「手机版」
 

LCA

LCA,最近公共祖先

博主今天回顾了倍增和Tarjan,总共用了40min码了两个模板(至少有20min在找Tarjan模板的错误,下面会讲到)

LuoGu模版题传送门

还是先说一下lca的暴力算法:两个节点一步一步往上跳,跳到同一个地方为止。。

1、倍增

在暴力算法上优化

发现暴力的缺陷:一步一步往上跳太慢。所以我们想到最好能一次跳一大步

先来看一个问题:给出一个数n,要求把n拆分成2的几次幂相加,求加数个数最少的一种方案

举个例子:n=36,36=32+4=16+16+4=16+8+8+4=1*36

反正有很多方案就对了,但加数个数最少的是32+4,加数个数为2,2就是倍增在36的复杂度;加数个数最多的是1*36,加数个数为36,36就是暴力在36的复杂度

再举几个例子:19+16+2+1,18+16+2,836=512+256+64+4

发现先从大的拆起,把这个思想放到树上就是先走大步再走小步

Code:

#include <bits/stdc++.h>
#define res register int
#define ll long long
#define maxn 500010
using namespace std;
struct Node{
    int to,next;
};
Node edge1[maxn<<1];
int head1[maxn<<1],n,m,root,d[maxn],fa[maxn][30],num1;

inline int read(){
    int s=0,w=1;
    char c=getchar();
    while (c<'0' || c>'9'){if (c=='-')w=1;c=getchar();}
    while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
    return s*w;
}
inline void add1(int x,int y){edge1[++num1].to=y;edge1[num1].next=head1[x];head1[x]=num1;}
inline void build(int u,int pre){
    d[u]=d[pre]+1; fa[u][0]=pre;
    for (res i=0;fa[u][i];++i) fa[u][i+1]=fa[fa[u][i]][i];
    for (res i=head1[u];i;i=edge1[i].next){
        int e=edge1[i].to;
        if (e!=pre) build(e,u);
    }
}
inline int lca(int u,int v){
    if (d[u]>d[v]) swap(u,v);
    for (res i=20;i>=0;--i) if (d[u]<=d[v]-(1<<i)) v=fa[v][i];
    if (u==v) return u;
    for (res i=20;i>=0;--i) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

int main(){
    n=read(),m=read(),root=read();
    for (res i=1;i<n;++i){
        int x=read(),y=read();
        add1(x,y); add1(y,x);
    }
    build(root,0);
    for (res i=1;i<=m;++i){
        int x=read(),y=read();
        printf("%d\n",lca(x,y));
    }
    return 0;
}

2、Tarjan

相对于倍增这个在线算法,Tarjan是一个离线算法

具体怎么做就是遍历整个树,不断更新节点的父亲,在某个节点,查询跟它有关的询问,若对方已经访问过,那么对方目前的祖宗就是对方到当前节点一路走来的拐弯处,而拐弯处其实就是lca

维护祖宗就是用并查集的

然后,我这里犯的一个错误就是:对于编号为i的询问(注意这里不是输入编号,而是链式前向星加询问时的编号),它对应的输入编号为(i+1)/2,我弄成了i

Code:

#include <bits/stdc++.h>
#define res register int
#define ll long long
#define maxn 500010
using namespace std;
struct Node{
    int to,next;
};
Node edge1[maxn<<1],edge2[maxn<<1];
int head1[maxn<<1],head2[maxn<<1],n,m,root,num1,num2,f[maxn],print[maxn];
bool vis[maxn];

inline int read(){
    int s=0,w=1;
    char c=getchar();
    while (c<'0' || c>'9'){if (c=='-')w=1;c=getchar();}
    while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
    return s*w;
}
inline void add1(int x,int y){edge1[++num1].to=y;edge1[num1].next=head1[x];head1[x]=num1;}
inline void add2(int x,int y){edge2[++num2].to=y;edge2[num2].next=head2[x];head2[x]=num2;}
inline int get(int k){return f[k]==k?k:f[k]=get(f[k]);}
inline void Tarjan(int u){
    vis[u]=1,f[u]=u;
    for (res i=head1[u];i;i=edge1[i].next){
        int e=edge1[i].to;
        if (!vis[e]){Tarjan(e); f[e]=u;}
    }
    for (res i=head2[u];i;i=edge2[i].next){
        int e=edge2[i].to;
        if (vis[e]) print[(i+1)>>1]=get(e);
    }
}
int main(){
    n=read(),m=read(),root=read();
    for (res i=1;i<n;++i){
        int x=read(),y=read();
        add1(x,y); add1(y,x);
    }
    for (res i=1;i<=m;++i){
        int x=read(),y=read();
        add2(x,y); add2(y,x);
    }
    Tarjan(root);
    for (res i=1;i<=m;++i) printf("%d\n",print[i]);
    return 0;
}

相关阅读

倍增求LCA模板

1.引入 点击转入模板题,by-luogu 2.思路 这道题目是倍增求LCA的模板题。 首先,大家都知道LCA的定义吧?(两个节点的公共父节点)如果我

分享到:

栏目导航

推荐阅读

热门阅读