LCT-学习笔记

~~为什么这种东西要我们自学...~~ ~~这几天再多做几道LCT的题~~ **LCT尽量少使用findroot操作**，如果经常用的话，可以使用并查集。 感谢[@FlashHu](http://www.cnblogs.com/flashhu/p/8324551.html)[@自为风月马前卒的博客](http://www.cnblogs.com/zwfymqz/p/8972914.html) LCT是Tarjan爷爷提出的超强算法，复杂度貌似是$O(N \log N)$，常数很大。 ## 能够解决的问题 1.求LCA 2.求最小生成树 3.维护**链上信息**：最大最小，链上和等 4.维护连通性 ~~5.优化单纯性算法，在$O(mn\log n)$的复杂度下求最大流~~ 既然是动态树，当然要支持动态加入、删除边咯。 ## 构造 解决树上问题时，由一种常见操作叫“链剖分”： - 重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子 - 长链剖分，并不是很常见，可以O(n)求每个点以深度为下标的信息 - 实链剖分，也就是LCT所用到的剖分方法 在实链剖分时，选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边。 与前两种剖分不同的是，实链剖分中的重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的，这就需要我们用更灵活一些的数据结构来维护。 我们使用平衡树来维护链上信息，splay最好。我们用splay维护每一条实路径(仅由实边组成的路径)，因为每条实路径都对应一条从根节点出发的链，这样的话路径上每个节点的深度都是不同的，因此在splay中，我们按深度作为关键字，对于一个节点，它的左孩子所**对应的原节点**深度比它小，右儿子所**对应的原节点**深度比它大。 但是这样的话，虽然每个节点都包含在了splay中，但是每个splay之间都是独立的，因此我们要考虑如何在各个splay中建立联系， 对于一个节点，假设它有三个儿子，其中最多有一个节点可以和他在一个splay中，另外两个儿子分别属于不同的splay。这里有一个非常巧妙的性质——另外两个儿子在他们所在的子树中一定是深度最小的，因此我们可以让每个splay中的根节点指向splay中 中序遍历编号最小(也就是原树中深度最小)的节点的父亲。 对于一棵这样的树  它的splay树可能长成这个样子  ## 基础操作 具体看那两个人的博客吧。 ### access 这里以access(n)为例：  我们自底向上执行access，我们对于每一个实链，现将N点的父亲splay到根，然后把父亲的右儿子（儿子的深度比自己大）置为N，直到N为根。 ```cpp il void access(int x) { for(ri y=0; x; x=fa[y=x]) splay(x),rs=y,up(x); } ``` 特地说一下splay操作： **rotate**： 一定要特判y是否为根，这样就不要改z的儿子；其他两行正常。记得pushup。 **splay**： 先自顶向下pushdown，然后正常rotate，但是到根的判断比较特殊。 ### makeroot 先access(x)，再splay(x)，这时x会成为splay的根节点，且x不含右儿子。但是根节点所在的splay中，根节点没有左儿子，怎么办？**翻转左右子树！** ### findroot 先accexx(x)，然后splay(x)，再不断的往左走，这样就可以找到x所在树的根节点了。 ### split(x,y) makeroot(x); access(y); splay(y); 一定要把一个点转到根才能取出整条链的信息！ ### link ```cpp il void link(int x,int y) { makert(x); if(findrt(y)!=x) fa[x]=y; } ``` ### cut ```cpp il void cut(int x,int y) { makert(x); if(findrt(y)==x&&fa[x]==y&&!rs) { fa[x]=ch[y][0]=0; up(y); } } ```