(非求差错)求教,为什么把link的时候pushup删了就对了?

回复帖子

@BeyondStars 2019-04-21 15:05 回复

rt,我之前的link这样写的

 void link(int x,int y){
     makeroot(x);fa[x] = y;pushup(y);
 }

然后pushup删了,成这样

 void link(int x,int y){
     makeroot(x);fa[x] = y;
 }

就AC了?想不通啊!多个pushup也不会有错啊?

@BFLSTiger 2019-05-03 08:26 回复 举报

可能是你其他地方的问题,因为我的代码多加个pushup也A了

@jiazhaopeng 2020-04-10 06:08 回复 举报

没有保证 $y$ 及其祖先的懒标记被下放。万一恰好 $y$ 有个懒标记,就可能用错误的儿子信息来更新 $y$ 的信息;再恰好下一步查询 $y$ 到 $y$ 的和,就会出错。

如果用模板题的方法,先判合法性,就加上 $pushup$ 也没有问题,因为那样会先 $Access(y)$, $y$ 及其祖先的懒标记就保证已经下放了。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。