61Link-Cut-Tree

Link-Cut-TreeLink-Cut-Tree(简称LCT)是解决动态树类问题一种数据结构神一般的Tarjan发明的(又是他注意动态树≠LCT，LCT只是解决动态树问题的一种数据结构LCT的基础是Splay(这里不区分SplayTree与Splay的区别)，但是二者不完全相同，直接套Splay的模板是很容易出错的先解决一个小问题维护一个序列，支持下列操作：区间求和区间求最值区间修改求连续子段和先解决一个小问题维护一个序列，支持下列操作：区间求和区间求最值区间修改求连续子段和这个线段树就可以解决具体做法不加累述了那么这个呢？维护一个序列，支持下列操作：区间求和区间求最值区间修改求连续子段和添加一段区间删除一段区间翻转一段区间NOI2005D1T2维修序列对Splay初学者来说几乎是噩梦级别的题目其实不难(笑Splay模板题(真心我们来看下一个问题维护一棵树，支持下列操作：链上求和链上求最值链上修改子树修改子树求和换根树链剖分将树进行轻重链剖分，然后重标号对重标号后的序列维护一棵线段树保证任意一个点到路径上的重链数不超过logn由于是DFS序所以子树修改和求和也是能做到的(换根的话如果在子树中求一下补集就行)最坏时间复杂度O(nlog^2n)在座的应该都会……吧？那么这个呢维护一棵树，支持下列操作：链上求和链上求最值链上修改断开树上的一条边连接两个点，保证连接后仍然是一棵树这就是一个简单的动态树问题由于树是动态的，我们不能每次操作都重标号一遍树链剖分搞不了了然而我们可以沿用树链剖分的轻重链剖分的概念既然是动态那么我们肯定要把静态的线段树换成动态的Splay于是就有LCT=树链剖分+Splay引入一些概念PreferredChild：重儿子(为了便于理解这里沿用树链剖分中的命名)，重儿子与父亲节点同在一棵Splay中，一个节点最多只能有一个重儿子PreferredEdge：重(zhòng)边，连接父亲节点和重儿子的边PreferredPath：重链，由重边及重边连接的节点构成的链AuxiliaryTree(辅助树)由一条重链上的所有节点所构成的Splay称作这条链的辅助树每个点的键值为这个点的深度，即这棵Splay的中序遍历是这条链从链顶到链底的所有节点构成的序列辅助树的根节点的父亲指向链顶的父亲节点，然而链顶的父亲节点的儿子并不指向辅助树的根节点原树与辅助树的关系原树与辅助树的关系原树中的重链-辅助树中两个节点位于同一棵Splay中原树中的轻链-辅助树中子节点所在Splay的根节点的father指向父节点注意原树与辅助树的结构并不相同辅助树的根节点≠原树的根节点辅助树中的father≠原树中的father原树与辅助树的关系由于要维护的信息已经都在辅助树中维护了，所以LCT无需维护原树，只维护辅助树即可轻链和重链并不是固定的，随着算法的进行，轻链和重链随算法需要和题目要求而变化，然而无论怎么变化，由这棵辅助树一定能生成原树，并满足辅助树的所有性质代码实现由于后续函数的讲解需要用到一些代码，故在此先将基本操作的代码列出鉴于某些小朋友觉得数组版实现起来并不难，所以在这里特意准备了指针版刁难他本人的结构体名习惯了就不要吐槽了与正常Splay不同的地方已用红字标出结构体声明structabcd{abcd*fa,*ls,*rs;int_variables_;int_operation_marks_;abcd(intx);voidPush_Up();voidPush_Down();void_Operate_();}*null=newabcd(0),*tree[M];/*_variables_是需要用到的变量_operation_marks_是需要打的标记_Operate_是需要进行的操作，如Reverse(),Add()等，不习惯写可以无视构造函数啥的自己写吧LCT没有查找功能，所以每个节点的地址都要记在一个指针数组里，直接调用null是空节点，可以不写，边界讨论恶心至极，自行定夺*/Push_Down()函数voidabcd::Push_Down(){if(fa-ls==this||fa-rs==this)fa-Push_Down();/*当前节点的标记只对当前子树生效由于找节点并非自上至下，故操作之前需预先将节点到辅助树根的标记全下传一遍由于父亲节点未必和当前节点在同一棵Splay中，所以要判断是不是父亲节点的儿子*/if(_operation_mark_!=_value_){ls-_Operate_();rs-_Operate_();_operation_mark_=_value_;}}Zig(x)/Zag(x)函数voidZig(abcd*x){abcd*y=x-fa;y-ls=x-rs;x-rs-fa=y;x-rs=y;x-fa=y-fa;if(y==y-fa-ls)y-fa-ls=x;elseif(y==y-fa-rs)y-fa-rs=x;y-fa=x;y-Push_Up();/*旋转直接沿用Splay的旋转方式，但是要加一些改动因为y节点可能既不是父亲的左儿子又不是父亲的右儿子，故两个if都不能省推荐不要写6行版本第五行不好讨论只需要对y进行Push_Up就行了，因为x还要继续旋转，到顶后再Push_Up即可Zag同理*/}Splay(x)函数voidSplay(abcd*x){x-Push_Down();//预先先将节点到根路径上的标记下传一遍while(x-fa-ls==x||x-fa-rs==x)//判断x是否为根的条件{abcd*y=x-fa,*z=y-fa;if(x==y-ls){if(y==z-ls)Zig(y);Zig(x);}else{if(y==z-rs)Zag(y);Zag(x);}}x-Push_Up();//x到根之后再Push_Up即可}/*这种Splay的方法只用4个旋转就完成了双旋的操作且无需讨论y和z之间的连边是不是重边推荐这么写若实在不习惯还请仔细讨论y和z的关系*/Access(x)函数Access(一些版本中也叫做Expose)函数，是LCT各种高难度动作的基础Access函数的作用是：将一个点与原先的重儿子切断，并使这个点到根路径上的边全都变为重边即执行Access(x)函数后这个节点到根的路径上的所有节点形成了一棵Splay便于操作或查询节点到根路径上的所有节点Access(x)函数voidAccess(abcd*x){abcd*y=null;while(x!=null){Splay(x);//先将x进行Splay移动到辅助树的根节点x-rs=y;//将x原有的重儿子切断，然后将y设为x的重儿子x-Push_Up();y=x;x=x-fa;}}//注意Access(x)之后x不一定是Splay的根节点所以Access之后通常还要Splay一下Move_To_Root(x)函数作用：将x设为原树的根有向树没有这个操作注意Access(x)之后x只是辅助树的总根，并不是原树的根，因为Access(x)之后x还有左子树，左子树的深度小于x，故x不是根节点发现x设为根之后，原先x到根的路径上点的深度正好反转于是只需要在Access+Splay之后翻转即可Move_To_Root(x)函数voidMove_To_Root(abcd*x){Access(x);Splay(x);x-Reverse();//↑这里不写这个函数可以手动翻转}Find_Root(x)函数作用：找到x所在辅助树的总根用于判断连通性，一些题不需要abcd*Find_Root(abcd*x){while(x-fa!=null)x=x-fa;returnx;}Link(x,y)函数作用：将x和y连接※有向图和无向图的写法不一样，有向图直接Access(x)之后切左儿子，无向图则需要Move_To_Root再连接一般的题都是无向图所以这里贴无向图代码voidLink(abcd*x,abcd*y){Move_To_Root(x);x-fa=y;}Cut(x,y)函数将x和y之间的连边切断直接将x进行Move_To_Root操作，然后将y进行Access+Splay，之后x一定在y的左儿子上，直接切断即可证明：反证法假设y进行Access+Splay操作时通过双旋将x旋转到y的左儿子的左儿子那么x和y之间一定有一个节点故xy之间深度之差不为1与已知xy之间有连边相矛盾Cut(x,y)函数voidCut(abcd*x,abcd*y){Move_To_Root(x);Access(y);Splay(y);x-fa=null;y-ls=null;y-Push_Up();}链上修改与查询对x到y路径上的点进行修改或查询只需要对x进行Move_To_Root操作，然后对y进行Access+Splay操作，那么x到y路径上的所有点都在以y为根的子树上，之后就随便搞了BZOJ2002弹飞绵羊题目大意：给定一个序列，每个点有一个权值a[i]，站在点i上会被弹到第i+a[i]个点上，支持单点修改操作，求从某个点出发经过多少次会被弹飞每个点的父亲节点是会被弹到的节点，显然可以得到一棵森林每个点的答案就是这个点的深度LCT维护size域即可BZOJ2049洞穴勘测题目大意：维护一座森林，支持连接一条边和删除一条边，多次询问两个点是否连通LCT判断森林的连通性，操作都很基础，不写挂就能过前提是不写挂BZOJ2631Tree题目大意：维护一棵树，提供四种操作：1.将x到y的路径上所有的点权值+z2.将x1到y1的边断开，然后将x2和y2链接，数据保证链接后仍然是棵树3.将x到y的路径上所有的点权值*z4.询问x到y路径上节点的权值和对51061取模真·LCT模板题，适合练手使用，当然写挂了挂一天也是有可能的对标记下传有问题的建议写完1798再处理这题BZOJ2843&&BZOJ1180题目大意：给定一座森林，每个点上有权值，支持以下操作：1.询问两个点是否联通，若不连通则链接一条无向边2.修改某个点的权值3.询问两点间路径上点权之和，若不连通输出impossible双倍经验题，操作也很裸，练手吧我会告诉你标程是Splay维护DFS序+启发式合并么BZOJ3091城市旅行题目大意：给定一棵树，每个点有一个点权，提供四种操作：1.删除两点之间的连边不存在边则无视2.在两点之前连接一条边两点已经联通则无视3.在两点之间的路径上所有点的点权加上一个数两点不连通则无视4.询问两点之间路径上任选两点路径上的点权和的期望值2752的LCT版本，具体细节去看我的题解，这里写不下BZOJ2594水管局长数据加强版题目大意：给定一个无向图，多次删除某条边，多次查询两点之间路径上边权最大值的最小值Link-Cut-Tree维护动态最小生成树将每条边变为一个点，点权为这条边的边权，连接原边两端点LCT维护最小生成树不支持删除操作，所以倒着做，先将所有没删除的边跑一遍Kruskal，然后再加点&&询问添加一条边时先判断两端点是否联通，若联通找到路径上边权最大的边，然后若这条边的边权比要加入的边大，删除该边，然后加进这条边BZOJ3514GERALD加强版题目大意：给定n个点m条边的无向图，询问当图中只有【编号在[l,r]区间内】的边存在时图中的联通块个数强制在线LCT维护动态最小生成树，先将每条边依次加