社区讨论
关于倍增LCA
P3302[SDOI2013] 森林参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lociqpxj
- 此快照首次捕获于
- 2023/10/30 14:28 2 年前
- 此快照最后确认于
- 2023/11/05 01:48 2 年前
CPP
int ling = log2(dep[x]);
for(int i=1;i<=ling;i++)
g[x][i] = g[g[x][i-1]][i-1];
在这道题中，这种写法会RE
题解解释说是
如果我们连边重构 update_LCA 时采用 lg[deep[u]] ，可能存在一种情况：这个点 i 原本的 ans[i][j]，j 最大已经大于了 lg[deep[u]] （即原来深度更深）
但是我们进行加边的时候，只会更新新加入的子树的倍增数组，而新加入的子树的depth只会增大不会减小吧，那为什么原来的深度会更深呢
望解答
回复
共 2 条回复，欢迎继续交流。
正在加载回复...