不懂就问:维护子树信息的 LCT Cut 操作
查看原帖
不懂就问:维护子树信息的 LCT Cut 操作
759459
flowing_boat楼主2024/4/28 22:53

rt

为何 Cut(x,y) 中:

这样是 100pts:

inline void Cut(int x, int y) {
			Access(y), Splay(y);
			ls(y) = fa(ls(y)) = 0; //<===this
			pushup(y);  
		}

这样是 RE。

inline void Cut(int x, int y) {
			Access(y), Splay(y);
			ls(y) = fa(x) = 0; //<===this
			pushup(y);  
		}

能理解静态树子树 LCT 不能 reverse() 但是这里为何必须是 fa(ls(y)) = 0 呢?

2024/4/28 22:53
加载中...