第一回写lct,问阿凡和线段钩把关键地方弄懂之后就很好写了,为了兼容我的splay风格,我看了至少三个风格完全不同的人的讲稿。
其中po姐ZigZag分开写的,不能忍。
ACDreamer是用tag来标记isroot,不懂。
还有就是毛爷爷的版本,和我的风格最为接近。于是综合几个版本一起看了看,把毛爷爷的板子改了改就和我的风格完全兼容了。

讲道理,lct使用splay维护多棵辅助树来实现那么多玄学的功能。

大概有一下几种操作:

  1. expose(x),使x到原树树根的所有边串成一个prefered path,到根的路径的所有点都在同一棵splay上,同时断开x与原来prefered child的联系。
  2. makeroot(x),使x成为所在原树的根,具体实现方法是expose(x); splay(x); reverse(x);
  3. link(u, v),在给出的u, v保证连边后原图仍为森林或树的情况下,将u, v连边,具体实现方法是makeroot(u); u->parent = v; expose(u);
  4. cut(u, v),在给出的u, v保证原来有边的情况下,将u, v间的边断开,具体实现方法是makeroot(u); splay(v); v->leftchild->parent = nil; v->leftchild = nil;
  5. findATRoot(x),找x所在辅助树的根,用于判断联通性,具体实现方法是不断的向上找parent,直到当前节点没有parent,则当前节点是辅助树的根。
  6. findroot(x),找x所在原树的根,具体实现方法是先expose(x),然后不断找x在splay上的左儿子,直到左儿子为nil,最后splay一下当前节点,当前节点为x所在原树的根。

注意所有往儿子找信息的时候都要pushdown

然后照例https://github.com/cjsoft/noip/tree/master/after_lnoi/d0530
其中lct.copy.cpp是比较规范的板,
lct.cpp不是太工整