题解 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
投递海康威视等公司10个岗位 >
