题解 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;
} 

好了以上就是全部 总而言之tarjan特别爽 建议理解后背下来 bye！

另外代码都是对的大家不用测试 也希望大家理解后写下来 不要ctrl+C+v