社区讨论

警示后人：如果你倍增LCA TLE

RRem_CandleFire
P7924「EVOI-RD2」旅行家参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m3wcyvny
此快照首次捕获于
2024/11/25 09:37
去年
此快照最后确认于
2025/11/04 13:58
4 个月前
查看原帖
这是一份普普通通的倍增LCA代码：
CPP
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
  if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
if(x==y) return x;
for(int i=19;i>=0;--i)
  if(fa[i][x]!=fa[i][y]) 
    x=fa[i][x],y=fa[i][y];
return fa[0][x];
这样会 T 飞。但是改成下面的代码就能过：
CPP
if(dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for(int i=19;i>=0;--i)
  if(t&(1<<i)) x=fa[i][x];
if(x==y) return x;
for(int i=19;i>=0;--i)
  if(fa[i][x]!=fa[i][y]) 
    x=fa[i][x],y=fa[i][y];
return fa[0][x];
二者的差距在于一个调用了过多的 dep 和 fa 数组，一个通过位运算枚举子集，前后时间差距 600ms。
请大家写 LCA 的时候选择更优秀的写法！！！

回复

共 4 条回复，欢迎继续交流。

正在加载回复...