关于倍增LCA
查看原帖
关于倍增LCA
307042
一Iris一楼主2021/3/21 09:43
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只会增大不会减小吧,那为什么原来的深度会更深呢

望解答

2021/3/21 09:43
加载中...