Top Tree

总归要学的。
先写一下理解比较困难的点。

1. 考虑 SATT 的建立过程：首先在树里面找到一个Compress Tree，这个树满足中序遍历写下来是根簇路径深度从小到大排列，然后根簇路径上挂着的小簇Rake起来，这个 Rake 的过程是容易的，考虑对于每一个直接连接的小簇，把他变成子问题，然后给一个代表点（Rake Node），和子问题的 Compress Tree 的根节点连接，然后这些代表点一个一个连在一起，依照合并顺序变成 Rake Tree，我们可以认为 Rake Node 代表的是这里有一个小簇等待连边，而很明显Compress结点和Rake结点万万不能混在一起，所以我们就他们内部用二叉树各自维护平衡（使用 Splay），而中间使用三叉树，用中间结点将他们连接。
2. 考虑信息的维护过程，我们已经用Rake Tree 将原树切割成了若干个 Compress Tree，也就是若干链，对于一个Compress Node，他的子树中的左右儿子代表的是他的当前子树簇路径的两个端点，而中儿子代表他挂的小簇的端点，这个是Rake下来的，考虑这个就是簇路径之外的点，于是我们可以用这个东西维护簇路径信息和簇信息，考虑我们能够通过expose强制把两个点塞根簇的端点里，也就是说我们可以这样维护路径信息，而子树信息也很好维护，因为我们可以维护子树簇内非子树簇路径的点的权值和，那我们只需要把点 x 做一次 access 之后对 x 的子树的非路径信息做操作，再合并 x 的信息即可，因为 x 是端点，端点的话子树内非簇信息就是子树啊。
3. Access 操作实际上是这样的，对于一个点他从属于一条 Compress Tree，而 Compress Tree 除非根簇上面都有一个 Rake Node，那么我们需要做得操作就是首先把当前点提到 Compress Tree 的根，然后操縦 Rake Node 到 Rake Tree 的根结点，这个时候我们再把 x 的父亲的父亲提到他所在的 Compress Tree 的根结点，此时如果这个点还有右结点，我们可以直接互换，否则的话我们就把 x 直接点过去并删除当前的 Rake Node。
   而原理也很易懂，考虑Compress Tree要求中序遍历下正好深度由当前钦点的同上层 Compress Tree 相连的结点往下递增，而我们做这样的操作的意思是，如果还有右端点（也就是在上一层的下端结点），就直接交换，将上一层的 Compress Node 作一个连接，相当于是将他的末尾端点引导过来，而上一层如果没有那就是延长末尾到当前簇，那当前簇就没必要再通过 Rake 操作进入树上了，可以直接进入上一层的 Compress Tree，所以我们直接删除当前的Rake结点即可。
   我们都知道根簇应该有两个端点，其中一个是根结点，而 Access(x) 的作用就是使 x 成为根簇中的非根结点端点，这个很有用的，而Makeroot(x) 的作用则是把 x 变成根簇的根结点端点注意到我们是可以控制根簇端点的，着可以让我们维护很多东西！
4. 连边和删边，其实也很简单，我们先做一下 makeroot(x)将 x 提到根结点，再access(y)将y提到根结点，具体区别见上，然后我们现在就是要在让两个根簇连接在一起，怎么连接呢，考虑相当于是做 compress 操作，x 现在是根结点而 y 现在是末尾，而具体路径结构是怎么接都不会变的，我们的需求是让路径的开头也就是 x和路径的结尾也就是 y 直接接到一起（具体操作是 y 的右儿子接 x）这样就认为连上了边！
   而基簇怎么办？基簇考虑对于Compress Tree，一个原树结点的作用是 Compress 或者是不做（端点），而 我们又知道对于一条边进入 Compress Tree 的方式只能是通过点的代表点，那这里结果就出来了，把基簇放到 x 的左儿子上，这样的话中序遍历合并整体就是对的，具体的合并是很优美的。

可惜 LCT 板子只需要我们维护点权，基簇维护与否我们根本不在乎，而 sone1 看着就炫酷很多啊！！！！太酷了吧，这个！