为什么 LCT 的 cut 不用 pushup
查看原帖
为什么 LCT 的 cut 不用 pushup
339128
Aigony楼主2023/9/12 14:42

RT,第一篇题解的 cut 函数是这么写的:

I cut(R x,R y){//断边
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!c[y][0]){
		f[y]=c[x][1]=0;
		pushup(x);
	}
}

但发现我自己的板子这个地方少一句 pushup,OIwiki 的代码在这个地方也没有 pushup。
同理,修改点权部分:

if(op==3) splay(x),tr[x].key=y;

感觉也应该有,但实际上的板子没有 pushup。

求助以上两个地方为什么这样写是对的。

2023/9/12 14:42
加载中...