题解 P3690 【【模板】Link Cut Tree （动态树）】

## [更好的阅读体验点这里](http://www.cnblogs.com/zwfymqz/p/8972914.html) ## 前置知识 - 必须要理解[splay](http://www.cnblogs.com/zwfymqz/p/7896036.html) - 最好学过[树链剖分](http://www.cnblogs.com/zwfymqz/p/8094500.html) ## 基础定义 LCT是一种解决动态树问题的方法，由tarjan~~(为什么又是他)~~在1982年提出，最原始的论文在[这里](https://pan.baidu.com/s/1eBpsyxQd7OAku_1dhzWjLA),在论文中，tarjan除了介绍了均摊复杂度为$O(log^2n)$的LCT之外，还介绍了一种严格$O(log^2n)$的算法，不过本人太弱了，看不懂tarjan讲了些啥，也没找到其他的学习资料，因此这种算法我们不做讨论 ## 能够解决的问题 1. 求LCA 2. 求最小生成树 3. 维护链上信息(最大最小，链上和等) 4. 维护联通性 5. 维护子树信息(需要配合AAA树) 6. 优化单纯性算法，在$O(mnlog(n))$的复杂度下求最大流（这两个是tarjan在它的论文最开头提到的，但是我除了在一本书中看到过有关的简介(没有代码)之外，再没看到过关于它的任何资料，） ## 构造 在解决树上问题的时候，有一种非常常见的操作叫做链剖分 链剖分一般分为三种 - 重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子 - 长链剖分，并不是很常见，可以$O(1)$求$k$级祖先，原理是把深度最深的儿子当做重(长)儿子 - 实链剖分，也就是LCT所用到的剖分方法，这里重点介绍一下 在实链剖分时，选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边。 与前两种剖分不同的是，实链剖分中的重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的，这就需要我们用更灵活一些的数据结构来维护。 维护一条链，我们首先可以想到的是链表，但是用链表来维护树上权值和的话时间复杂度肯定是$O(n^2)$的，即使是块状链表也只能做到$O(n \sqrt{n})$ 因此我们用平衡树来维护链上信息，那么用什么平衡树呢？理论上splay和fhq treap都是可以的，treap不可以，因为不能维护翻转信息，在这里我比较推荐splay，因为网上有关LCT的题目大多数题解都是用splay写的，这样的话学习难度也会小一点，而且我自测splay的常数要比fhq treap小很多 我们用splay维护每一条实路径(仅由实边组成的路径)，因为每条实路径都对应一条从根节点出发的链，这样的话路径上每个节点的深度都是不同的，因此在splay中，我们按深度作为关键字，对于一个节点，它的左孩子所**对应的原节点**深度比它小，右儿子所**对应的原节点**深度比它大 （这里插一句闲话，LCT之所以难于理解，很大程度上是初学者分不清原树/splay，因此我希望大家在继续往下读的过程中，一定要分清楚我所说的概念到时指的是原树还是splay树） 但是这样的话，虽然每个节点都包含在了splay中，但是每个splay之间都是独立的，因此我们要考虑如何在各个splay中建立联系， 对于一个节点，假设它有三个儿子，其中最多有一个节点可以和他在一个splay中，另外两个儿子分别属于不同的splay。这里有一个非常巧妙的性质——另外两个儿子在他们所在的子树中一定是深度最小的，因此我们可以让每个splay中的根节点指向splay中 中序遍历编号最小(也就是原树中深度最小)的节点的父亲，有点绕，希望大家好好理解一下 对于一棵这样的树 (图片来源：FlashHu的博客)  它的splay树可能长这个样子  ## LCT基础操作 ### $access(x)$ 将根节点到$x$点的路径变为实路径，且$x$与其儿子之间的边都变为虚边。 首先考虑一下这个操作有什么目的，有了这个操作，我们就可以将根节点到$x$的这条路径放在同一棵splay中，这样可以很方便通过在splay上打标记得到路径信息 具体怎么实现呢？ 还是上面那张图  如果我们要执行$access(N)$， 我们可以从下往上依次处理，首先我们要使得$N-O$这条边变为轻边，因为在splay中，节点的深度是唯一的，所以我们首先把$N$，转到根节点，这样它右边的节点一定是$O$，然后直接把$N$节点的右儿子置为$0$就可以了 继续往上，我们需要使$I-K$这条边变为轻边，同时使$I-L$这条边变为重边 考虑如何使$I-K$变为轻边。和上面的思路一样，我们首先使$I$转到所在splay的根节点，这样的话它的右儿子一定是$K$，然后我们只需要断开$I-K$这条边即可 考虑如何使$I-L$变为重边。这个就so easy了，直接将$I$的右儿子置为$L$即可 此时$I$所在的splay的父亲指向$H$ 继续往上思路就是一样的了，按照同样的套路使得$H-J$变为轻边，使$H-I$变为重边， 此时$H$指向$A$，然后让$A$转到所在splay的根节点，把右儿子置为$H$即可 这样我们就实现了$access$操作，按照上面的流程，我们不难总结出算法框架 1. 将要处理的节点转到根 2. 更改右儿子 3. 更新标记 代码的话，，首先说一下各种定义 ```cpp struct node { int f, ch[2], s; //f：父亲 //ch[0]/[1]:左/右儿子 //s:标记，依题目而变 bool r;//是否翻转 }T[MAXN]; ``` access ```cpp void access(int x) {//访问x节点 for(int y = 0; x; x = fa(y = x)) splay(x), rs(x) = y, update(x); //首先把x splay到所在平衡树的根，这样可以保证它的右孩子就是在原树中对应的重链(右孩子深度比它大) //y是splay中x的儿子，把x的右儿子改成y，也就是把x和y之间的边变成实边 //更改了节点顺序，需要update } ``` ### $makeroot(x)$ 将$x$变为原树的根 考虑这个操作的意义。对于大多数树上询问来说，都是询问一条过根节点的路径，由于LCT的构造的缘故，这种询问处理起来非常麻烦。但是当询问的一端在根节点的时候，处理起来就容易的多，所以这个操作的意义在于帮助我们更好的处理询问 这里有一个非常巧妙的实现思路： 首先我们需要$access(x)$，这样我们就把根节点和$x$放到了同一棵splay中 此时$x$是不含右儿子的（没有深度比他大的点） 然后我们需要$splay(x)$，此时$x$会成为splay的根节点，且$x$不含右儿子。 但是在根节点所在的splay中，根节点没有左儿子（没有深度比他小的节点） 这可怎么办呢？？ 这里就有一个骚操作了，我们直接将$x$的左右子树翻转！ 这样$x$不就没有左儿子了么？233 事实证明这样是对的 代码： ```cpp void makeroot(int x) {//把x改为原树的根节点 access(x); splay(x); T[x].r ^= 1;//更新翻转标记 } ``` ### $findroot(x)$ 找到$x$所在原树的根 你刚开始可能跟我一样很呆萌的认为：$x$所在原树的根不就是根节点么？ 但是。。 有一点需要注意：LCT维护的是森林，也就是很多棵树，因此每个节点所在原树的根节点往往是不同的 考虑这个操作的意义： 大家有没有发现，这个操作跟并查集中找祖先的操作很类似？没错，这个操作的用处就是判断两个节点的联通性（是否在同一棵树上） 实现的话，我们利用了一个性质：一棵树的根节点一定是深度最小的点 这样我们先$accexx(x)$，然后$splay(x)$，再不断的往左走，这样就可以找到$x$所在树的根节点了！ 注意！往左走的时候一定要下传标记，否则在某些题目中你会挂的很惨！ 代码 ```cpp int findroot(int x) {//找到x在原树中的根节点 access(x);splay(x); pushdown(x); while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点 return x; } ``` ### $split(x,y)$ 获取到$x-y$所对应的路径， 这个操作的意义就非常显然了 实现也非常好想，直接上代码吧 这样的话可以通过访问$y$节点来获取到有关路径的信息 ```cpp void split(int x, int y) { makeroot(x);//首先把x置为根节点 access(y); splay(y); //然后访问一下y，再把y转到根节点，这样y维护的就是x - y 路径上的信息 } ``` ### $link(x,y)$ 连接$x,y$ 这个操作的意义也很显然 首先我们需要$makeroot(x)$，然后$access(y),splay(y)$，最后把$x$的父亲指向$y$就可以 注意在一些毒瘤题中不保证$x,y$未联通，这样还需要判断一下联通性 ```cpp void link(int x, int y) { makeroot(x);//把x置为根节点 if(findroot(y) != x ) fa(x) = y; //如果x与y不在同一个splay中，就把y置为x的父亲 //findroot(y)的时候已经执行了access(y),splay(y) } ``` ### $cut(x,y)$ 断开$x-y$这条边 意义也非常显然 实现的话看上去比较容易 我们需要$split(x,y)$，此时$x$的父亲是$y$，$y$因为是深度最深的点，所以它的左儿子是$x$， 然后断绝父子关系就好了 但是！！，如果出题人不保证$x-y$相连呢？？ 如果仍然这样改的话整棵树就乱了 因此我们还要加一坨判断 1. 首先$x,y$一定要在一棵树内 2. $x$的父亲是$y$，且$y$的左儿子是$x$ 这两个比较显然 3. $x$没有右儿子 这个可能就不是那么显然了 我们仔细考虑一下，$x$的右儿子代表着深度比他大的节点，$y$的左儿子代表着深度比他小的节点 那如果出现这种情况呢？  然后我们就GG了， 或者你可以试试这组数据 ```cpp 5 6 1 2 3 4 5 1 1 2 1 2 3 1 3 4 1 4 5 2 1 5 0 1 5 ``` 因此我们有必要加上这个判断 代码： ```cppp void cut(int x, int y) { makeroot(x); if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) { fa(x) = T[y].ch[0] = 0; update(y); } } ``` ## 时间复杂度 以上操作的平摊复杂度均为$O(log^2N)$ 具体的证明可以参考YangZhe的论文 ## 小结 LCT的操作也就是这么多了， 不过LCT有很多拓展，题目类型也有很多，大部分我还没做过 等以后慢慢整理吧 洛谷的板子题代码： 其中的splay和rotate都是我自己yy的，并不是很主流的写法，不过跑的比较快 ```cpp // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> #define swap(x,y) x ^= y, y ^= x, x ^= y const int MAXN=3 * 1e5 + 10; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();} return x * f; } #define fa(x) T[x].f #define ls(x) T[x].ch[0] #define rs(x) T[x].ch[1] int v[MAXN]; struct node { int f, ch[2], s; bool r; }T[MAXN]; int ident(int x) { return T[fa(x)].ch[0] == x ? 0 : 1;//判断该节点是父亲的哪个儿子 } int connect(int x,int fa,int how) { T[x].f=fa; T[fa].ch[how]=x;//连接 } inline bool IsRoot(int x) {//若为splay中的根则返回1 否则返回0 return ls( fa(x) ) != x && rs( fa(x) ) != x; //用到了两个性质 //1.若x与fa(x)之间的边是虚边，那么它的父亲的孩子中不会有他（不在同一个splay内） //2. splay的根节点与其父亲之间的边是虚边 } void update(int x) { T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x];//维护路径上的异或和 } void pushdown(int x) { if(T[x].r) { swap(ls(x),rs(x)); T[ls(x)].r ^= 1; T[rs(x)].r ^= 1; T[x].r = 0;//标记下传 } } void rotate(int x) { int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y); int B = T[x].ch[Yson ^ 1]; T[x].f = R; if(!IsRoot(Y)) connect(x, R, Rson); //这里如果不判断y是否根节点，那么当y是根节点的时候，0节点的儿子就会被更新为x //这样x就永远不能被判断为根节点，也就会无限循环下去了 //但是这里不更新x的父亲的话就会出现无限递归的情况 connect(B, Y, Yson); connect(Y, x, Yson ^ 1); update(Y); update(x); } int st[MAXN]; void splay(int x) { int y = x, top = 0; st[++top] = y; while(!IsRoot(y)) st[++top] = y = fa(y); //用一个栈维护所有的标记 while(top) pushdown(st[top--]); //因为在旋转的时候不会处理标记，所以splay之前应该下传所有标记 for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))//只要不是根就转 if(!IsRoot(y)) rotate( ident(x) == ident(y) ? x : y ); } void access(int x) {//访问x节点 for(int y = 0; x; x = fa(y = x)) splay(x), rs(x) = y, update(x); } void makeroot(int x) {//把x改为原树的根节点 access(x); splay(x); T[x].r ^= 1; pushdown(x); } int findroot(int x) {//找到x在原树中的根节点 access(x);splay(x); pushdown(x); while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点 return x; } void split(int x, int y) { makeroot(x);//首先把x置为根节点 access(y); splay(y); } void link(int x, int y) { makeroot(x);//把x置为根节点 if(findroot(y) != x ) fa(x) = y; } void cut(int x, int y) { makeroot(x); if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) { fa(x) = T[y].ch[0] = 0; update(y); } } int main() { #ifdef WIN32 freopen("a.in","r",stdin); //freopen("a.out","w",stdout); #else #endif int N = read(), M = read(); for(int i = 1; i <= N; i++) v[i] = read(); for(int i = 1; i <= M; i++) { int opt = read(), x = read(), y = read(); if(opt == 0) split(x, y), printf("%d\n",T[y].s); else if(opt == 1) link(x, y); else if(opt == 2) cut(x, y); else if(opt == 3) splay(x), v[x] = y; } return 0; } ``` ## 参考资料 [FlashHu的博客](http://www.cnblogs.com/flashhu/) [YangZhe-QTREE解法的一些研究](https://wenku.baidu.com/view/75906f160b4e767f5acfcedb) 《高级数据结构》-林厚从