LCT 无 Makeroot 函数时如何进行 cut 操作
  • 板块P5212 SubString
  • 楼主fjy666
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/6/15 13:53
  • 上次更新2023/10/23 13:07:06
查看原帖
LCT 无 Makeroot 函数时如何进行 cut 操作
366338
fjy666楼主2023/6/15 13:53

我看了题解,是这么维护的

inline void Cut(int x){
    Access(x);splay(x);
    //maintain some information
    t[lc].fa=0;lc=0;
}

把 xx 和 xx 的父亲的边断掉了。
但是有没有神仙给我解释一下为什么 lclc 就是 xx 的父亲啊,xx 的父亲不能在 lclc 的右子树内吗/yiw

经过 assert 测试,lclc 的右子树为 00。但是为什么呢?

2023/6/15 13:53
加载中...