2019-07-28 08:51 南非加里敦大学附属小学 C++

关注

题解 P3379 【【模板】最近公共祖先（LCA）】

蒟蒻学了lca 写篇题解加强理解也方便大家也建议大家都可以这样试试理解会更深刻

我自己的代码风格是主函数非常清晰简短主要靠自写函数

lca的做法主要来说有三种：

1.倍增

2.lca转rmq

3.Targan

这些的原理dalao们已经讲得足够清楚了蒟蒻也不能说的更清晰了主要说一下三种的特点与代码的细节

(PS:我是真的写的很认真求通过呀)

特别提醒请从1.0看起会讲解代码风格

1.0 倍增

用时: 1399ms / 内存: 53552KB

~~看到这么大的用时与内存是不是很可怕~~

但是实际上来讲用了读入与输出优化后过这题是~~妥妥的~~

●特点

倍增的特点就是用2的n次方向上爬爬到同一层后一起向上爬虽然比一个一个爬快了许多但是还是不够优秀

在线处理

●函数讲解

○读入与输出优化

注意的是因为我们是有信仰的oier 所以相信位运算更快

/**读入优化**/
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
    return;
}
/**输出优化**/
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
    return;
}

○邻接表储存

/**邻接表储存 tot记总数 head标准用法**/
int tot,head[maxn];
struct node{
    int next,v;
}e[maxn*2];
void add(int x,int y)
{
    tot++;
    e[tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}

○dfs

主要目的在初始化 f数组便于跳

/**dfs部分 dep记深度 f为[n节点][跳二的次方步]的父亲**/
int dep[maxn],f[maxn][20];
inline void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1;(1<<i)<=dep[x];i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
    }
}

○lca

~~上一步已经帮我埋好了伏笔我再不跳是不是对不起上个函数呀~~

/**lca 将深度大的跳到与深度小的同一层深度处**/
inline int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]];
    /**这个while非常骚气 保证跳到同一层同时不会乱辈分**/
    if(x==y) return y;
    /**已经是自己了下面就没有意义了**/
    for(int i=lg[dep[x]];i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}

○主函数

int main()
{
    read(n); read(m); read(rt);
    /**有信仰的读优**/
    for(int i=1;i<n;i++)
        read(a),read(b),add(a,b),add(b,a);
    /**读入部分建立双向边**/
    for(int i=2;i<=n+1;i++)
        lg[i]=lg[i>>1]+1;
    /**预处理以2为底的log函数 （速度小于调用 log2（） ）**/
    dfs(rt,0);
    /**rt为限定了的根 0默认为根的父亲 其深度为0**/
    for(int i=1;i<=m;i++)
        read(a),read(b),print(lca(a,b)),puts("");
    /**lca 进行查找**/
    return 0;
    /**华丽结束**/
}

●ps

对于该做法来说坑点和需要特别注意的点很少基本上不会出错除了费时间没有什么不够优秀的
唯一需要小心的就是双向边存储内存开两倍

●完整代码

~~知道你们一直在等这个~~

/**lca**倍增做法**/
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int lg[maxn],n,m,a,b,rt;
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
    return;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
    return;
}
int tot,head[maxn];
struct node{
    int next,v;
}e[maxn*2];
void add(int x,int y)
{
    tot++;
    e[tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}
int dep[maxn],f[maxn][20];
inline void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1;(1<<i)<=dep[x];i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
    }
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]];
    if(x==y) return y;
    for(int i=lg[dep[x]];i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    read(n); read(m); read(rt);
    for(int i=1;i<n;i++)
        read(a),read(b),add(a,b),add(b,a);
    for(int i=2;i<=n+1;i++)
        lg[i]=lg[i>>1]+1;
    dfs(rt,0);
    for(int i=1;i<=m;i++)
        read(a),read(b),print(lca(a,b)),puts("");
    return 0;
}

2.0 st表（lca转rmq）

用时: 1528ms / 内存: 99516KB

~~害怕居然比倍增慢那我还学个p呀~~

我们要重在学习方法与思路

●特点

st表需要找到这棵树的dfs序即dfn数组然后记录第一次出现的位置之后在位置之间寻找深度最小的点

注意f数组需要存的是点的id

●函数讲解

○读入输出优化&&邻接表跳过（同1.0）

○dfs（求欧拉序）

在其他大佬们的证明下，dfn的原因想必大家已经知道了但是注意的是dfn存的是点的编号

inline void dfs(int x,int fa)
{
    dfn[++cnt]=x;
    dep[x]=dep[fa]+1;
    pos[x]=cnt;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
        dfn[++cnt]=x;
    }
}

○对rmq进行预处理

注意：此处的比较带入dep数组但是存的依然是点的编号！

inline void rmq()
{
    /**f为从后下标开始向后推2的前下标次方个值深度最小的值的点**/
    for(int i=1;i<=cnt;i++)
        f[0][i]=dfn[i];
    /**2的0次方等于1 及它本身就是该值**/
    for(int i=1;i<=20;i++)
    /**根据本题 次方开到20（超百万）保过**/
        for(int j=1;j+(1<<i)-1<=cnt;j++)
        {
            /**注意 比较用的深度 存储用的名称**/
            if(dep[f[i-1][j]]<dep[f[i-1][j+(1<<(i-1))]])
                f[i][j]=f[i-1][j];
            else
                f[i][j]=f[i-1][j+(1<<(i-1))];
        }
}

○lca提取所需要的值

这是rmq的模板了不会的可以去做做模板题

inline int lca(int x,int y)
{
    x=pos[x];
    y=pos[y];
    if(x>y) swap(x,y);
    int k=lg[y-x+1];
    if(dep[f[k][x]]>dep[f[k][y-(1<<k)+1]]) return f[k][y-(1<<k)+1];
    else return f[k][x];
}

○主函数

大体上于1.0相同

int main()
{
    read(n); read(m); read(rt);
    for(int i=1;i<n;i++)
        read(a),read(b),add(a,b),add(b,a);
    dfs(rt,0);
    /**根据cnt的数对log进行处理**/
    for(int i=2;i<=cnt;i++)
        lg[i]=lg[i>>1]+1;
    rmq();
    for(int i=1;i<=m;i++)
        read(a),read(b),print(lca(a,b)),puts("");
    return 0;
    /**华丽结束**/
}

●完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int lg[maxn<<2],n,m,a,b,rt;
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
    return;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
    return;
}
int tot,head[maxn];
struct node{
    int next,v;
}e[maxn<<1];○
inline void add(int x,int y)
{
    tot++; 
    e[tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}
int cnt;
int dep[maxn],pos[maxn],dfn[maxn<<1],f[20][maxn<<1];
inline void dfs(int x,int fa)
{
    dfn[++cnt]=x;
    dep[x]=dep[fa]+1;
    pos[x]=cnt;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
        dfn[++cnt]=x;
    }
}
inline void rmq()
{
    for(int i=1;i<=cnt;i++)
        f[0][i]=dfn[i];
    for(int i=1;i<=20;i++)
        for(int j=1;j+(1<<i)-1<=cnt;j++)
        {
            if(dep[f[i-1][j]]<dep[f[i-1][j+(1<<(i-1))]])
                f[i][j]=f[i-1][j];
            else
                f[i][j]=f[i-1][j+(1<<(i-1))];
        }
}
inline int lca(int x,int y)
{
    x=pos[x];
    y=pos[y];
    if(x>y) swap(x,y);
    int k=lg[y-x+1];
    if(dep[f[k][x]]>dep[f[k][y-(1<<k)+1]]) return f[k][y-(1<<k)+1];
    else return f[k][x];
}
int main()
{
    read(n); read(m); read(rt);
    for(int i=1;i<n;i++)
        read(a),read(b),add(a,b),add(b,a);
    dfs(rt,0);
    for(int i=2;i<=cnt;i++)
        lg[i]=lg[i>>1]+1;
    rmq();
    for(int i=1;i<=m;i++)
        read(a),read(b),print(lca(a,b)),puts("");
    return 0;
}

3.0 Targan

用时: 708ms / 内存: 30140KB

这里必须要膜拜一下Targan了%%%%%

●特点

Targan做法的精髓在使用并查集进行了处理外加v数组进行判断不但节省时间而且空间也是妥妥的呀！

tarjan不同的在于是离线处理一次搞完所有的然后用ans数组输出

因此需要注意保持顺序

tarjan建了两个邻接表一个是询问的一个是输入的函数部分具体讲解

●函数讲解

○读优输优省略

○邻接表

~~如果分不清哪个是哪个就好好取名字不然分不清的时候不要骂博主~~

/**运用两组邻接表 建立两张图 没有1是二叉树同前 有1是查询**/
int tot,tot1,head[maxn],head1[maxn];
struct node{
    int v,next;
}e[maxn<<1];
struct node1{
    int v,next,num;
}e1[maxn<<1];
/** 双向边 空间*2 **/
inline void add(int x,int y)
{
    tot++;
    e[tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}
inline void add1(int i,int x,int y)
{
    /**特别说明：i为输出的关键词 记录的是顺序**/
    tot1++;
    e1[tot1].v=y;
    e1[tot1].next=head1[x];
    e1[tot1].num=i;
    head1[x]=tot1;
}

○并查集

int f[maxn];
inline void unionn(int x,int y)
{
    /**合并**/
    f[x]=y;
}
inline int find(int x)
{
    /**找父亲**/
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

○dfs

！！！千万注意！！！返回的时候v再给1 不然遇到找自己的就凉了！

inline void dfs(int x,int fa)
{
    /**第一次循环标记 v及访问过的点**/
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
        unionn(e[i].v,x);
    }
    v[x]=1;
    /**查找当前标记点的对象有没有以被标记了的**/
    for(int i=head1[x];i;i=e1[i].next)
    {
        if(v[e1[i].v]==0) continue;
        ans[e1[i].num]=find(e1[i].v);
    }
}

○主函数

注意的是如果遇到多组数据同时出现 f数组不需要清0 会重新复制的

int main()
{
    read(n); read(m); read(rt);
    for(int i=1;i<n;i++)
        f[i]=i,read(a),read(b),add(a,b),add(b,a);
    f[n]=n;
    /**为了减少一次循环 将f（并查集）在读入时进行处理**/
    for(int i=1;i<=m;i++)
        read(a),read(b),add1(i,a,b),add1(i,b,a);
    dfs(rt,0);
    for(int i=1;i<=m;i++)
        print(ans[i]),puts("");
    return 0;
}

●完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int n,m,a,b,rt,ans[maxn],v[maxn];
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
    return;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
    return;
}
int tot,tot1,head[maxn],head1[maxn];
struct node{
    int v,next;
}e[maxn<<1];
struct node1{
    int v,next,num;
}e1[maxn<<1];
inline void add(int x,int y)
{
    tot++;
    e[tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}
inline void add1(int i,int x,int y)
{
    tot1++;
    e1[tot1].v=y;
    e1[tot1].next=head1[x];
    e1[tot1].num=i;
    head1[x]=tot1;
}
int f[maxn];
inline void unionn(int x,int y)
{
    f[x]=y;
}
inline int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
inline void dfs(int x,int fa)
{
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x);
        unionn(e[i].v,x);
    }
    v[x]=1;
    for(int i=head1[x];i;i=e1[i].next)
    {
        if(v[e1[i].v]==0) continue;
        ans[e1[i].num]=find(e1[i].v);
    }
}
int main()
{
    read(n); read(m); read(rt);
    for(int i=1;i<n;i++)
        f[i]=i,read(a),read(b),add(a,b),add(b,a);
    f[n]=n;
    for(int i=1;i<=m;i++)
        read(a),read(b),add1(i,a,b),add1(i,b,a);
    dfs(rt,0);
    for(int i=1;i<=m;i++)
        print(ans[i]),puts("");
    return 0;
}