Link Cut Tree对我来说已经有点老生常谈了——目前为止理解的比较深的一种比较难的数据结构吧。

        之前的初探以及次探已经基本阐明了LCT本身的功能和大部分的作用，在这里做一个简单点的回顾吧。



        首先就是数据结构本身。LCT又叫做动态树，本身很像树链剖分+SplayTree，但是如其名，可以动态的变化。主要函数就是Access(expose)、Splay和Reverse。初始状态的时候，所有的点都自成一个SplayTree，每一个点都是一个SplayTree的root，于是就有了判根函数isroot(x)，如果是根，那么x本身没有有fa或者fa的右儿子不是是它。然后Access(x)无非就是一个合并的过程，一次性把从根到x的所有节点合并到一个SplayTree中。然后函数Splay(x)就是把x旋转到x所在的树的根。然后Reverse(x)就是把整个树进行翻转，即原本的fa变成儿子，表现在SplayTree中就是每个节点的左右儿子对调，每次修改的时候打上rev标记不直接修改。



        其次，就是一些应用。最主要的就是进行一些链上的操作，或者说树上两点路径的操作。对于两点(x,y)，我可以维护之间的最大值、最小值以及和。实现方式则是首先Access(x)，再Splay(x)，然后Access(y)，最后Splay(y)，答案就在y节点中。画出图来解释就是，首先把根与x的链拿出来，再把x的一头拎起来变成根，然后把根x与y的链拿出来。到这一步，我们发现，拿出来的链就已经是从x到y的路径了。最后再把y拎起来作为根，把修改的标记打到根y上，就完成了修改。对于询问也是类似的，当然，这些操作依赖于在Access和Splay过程中对节点数据和标记的不断更新(push_up)和下传(push_down)。这个具体看BZOJ 2243(Link Cut Tree解法) 这里面的代码。注意在Splay旋转前，要从根开始顺着链下放所有的标记。



        然后还有一个叫基环树森林的东西，就是一些东西有相互依赖的关系，可能会形成环，但是我们通过保存虚边的方式去掉一些边，使得还能够保持树的性质。当然了，要求仍然是每个点只能有一个fa。这种情况下，对连接关系的动态修改就要分一些情况进行讨论。如果切断一个点的时候，如果原本有一条虚边被保存没有连接，那么我们就可以现在把他们连起来，当然了要看虚边的另一头是哪个点，如果恰好是删掉的点，那么当然不能连。用一个数组保存没有连接的虚边，在连接的时候也提前判断两个点是否已经连接，如果已经连接，那么这条边显然要作为虚边保存。这个具体可以看 HDU 5967 小R与手机 里面的代码，已经写到模板里面了，可以直接用。之前还有一个BZOJ 2759的代码，写的不如这个简洁。



       接着，还有一个很好的应用，就是一个动态的缩点。普通的tarjan和kosaraju算法求连通分量缩点都是只能离线的求，遇到动态问题完全没有办法，LCT却可以解决这个问题。LCT利用它的Link和Cut灵活的特点可以模拟出加边和去边的过程，然后缩点无非就是因为成环了，我在LCT加边的时候完全可以判断出来。一旦发现连边成环之后，我环上所有的点显然就是可以缩点成为一个新的点。用并查集取维护每一个点在缩点之后属于的点，问题的关键就在于如何合并。其实想那么多干嘛，直接暴力合成就行了，把环上所有的点并查集合并到新的点中，甚至边的关系都不用改了（直接在指向外面套上一个f[]即可）。这个具体可以看17年沈阳网络赛的 HDU 6200 mustedge里面的代码。



       最后，我想说，今天的重点还没来。之前说的东西，以及函数Access()等一些东西，好像都是对树上的路径做文章，LCT就真的局限于做这些树链上的东西吗？其实LCT强大的很，对于子树的东西也是可以维护的。链上维护的时候，每个节点保存的数值严格都取自于所在的SplayTree中，即SplayTree之外的点的数据不会用到。为了达到这个目的，每次都会用push_up对所求的数据进行重算。但是在进行子树维护的时候可以用Splay之外的数据，所有不是重算，而是一个不断累积的过程。同样利用标记从根开始往下传递修改。然后在还是Splay之前顺着链下放标记。然后对于子树LCT毕竟还是有局限的，虽说也可以求极值，但是在修改的时候限制很多，求和也不能做到整个子树的修改。这个具体看 BZOJ 2555 Substring 的代码。



        最后的最后说说我自己的小疑问。首先，是这个时间复杂度的问题，根据大神们的分析，LCT均摊的时间复杂度均摊可以到O(MlogN)，其中M为操作数，N为节点数，在这里给一个自认为写的很好的分析 。然后实际测试效果也是很好，10^5的数据都能够比较快的通过。一开始我认为在进行链上修改的时候，两个Access其实是把两个点之间的路径给遍历了一遍，如果链状数据，复杂度貌似会退化到O(MN)。但是其实我们Access操作一般还跟着Splay操作，意味着树的根时刻在变化，与SplayTree类似，复杂度就被均摊了，所有说还是O(MlogN)。另外，就是对于Reverse的应用。我知道对于有向树，是不需要用Reverse的，但是实际中除了需要记录深度的时候，还有什么时候需要用到整个翻转的操作。个人感觉用的地方也不多。对于这两个问题，不知道是不是我的理解有误，希望能得到会的大神的指正咯O(∩_∩)O……