树链剖分有一个更专业的名称 ：轻重链剖分，即为根据子节点的子树大小来剖，虽然树链剖分有很好的性质 ，但是还是存在缺陷的。例如 ： 树链剖分将树剖完之后是静态的，（无法进行修改了，但不代表就不能换根了。）也就是说树链剖分只能针对于树的结构不变的情况下操作。
实链剖分 ： 将树的边分为两种，一种是实边，一种是虚边，维护的时候则是对实边进行维护。
我们发现实链剖分很不固定，将树的边划分实虚的话，也无法保证形态。如果我们用一个灵活的数据结构，那么我们发现，其实这个树完全可以动起来，因为任意转化实虚边都可以维护，也就是说，删除一条边，加上一条边，对于实链剖分来说，都可以。
然后我们将实链剖分剖出来的链用 维护，这种数据结构叫做 即 。
不知道为什么 的一些博客讲解中以 去维护轻重链剖分的链。
大概有辅助树， 与辅助树的关系之类。
辅助树
可以简单的理解为一些 构成了辅助树。我们给出一张图来理解一下其结构 ：
通过对比第一个图和第二个图，我们可以知道原树中的实链对应着辅助树的实链。无论怎么变换都是一条条的实链都是不会变得。
同时，因为我们选择用 维护一条实链，那么我们也就可以认为左边绿框框也就是一个 , 然后我们显然可以知道这些 是通过虚边连接起来的（也就是红边连接起来的）。
然后我们考虑是怎么构造的这一颗辅助树 ：
首先我们通过实链构造出一颗颗的 , 即为 ：
总共三个
然后我们令 去寻找他在原树中的父亲，也就是 , 然后通过虚边连接起来。
这里有一个不成文的规定 ： 认父不认子
最后就构造完了。
辅助树和原树的区别
- 辅助树的根不一定是原树的根。
- 原树父亲的指向不等同于辅助树父亲的指向
- 辅助树是可以在 的帮助下，实现任意换根。
- 辅助树中不存在节点指向子节点的情况。（但可以有节点统计子节点的情况）
- 每一个 维护的是一条在原树中深度严格递增的树链，且中序遍历 得到的每一个点的深度组成的序列也是严格递增的。
- 每一个节点包含且仅包含于一个 中
- 认父不认子
边分为实边和虚边，实边包含在 中，而虚边总是由一棵 指向另一个节点（指向该 中中序遍历最靠前的点在原树中的父亲）。
因为性质 ，当某点在原树中有多个儿子时，只能向其中一个儿子拉一条实链（只认一个儿子），而其它儿子是不能在这个 中的。
那么为了保持树的形状，我们要让到其它儿子的边变为虚边，由对应儿子所属的 的根节点的父亲指向该点，而从该点并不能直接访问该儿子（认父不认子）。
Access(x) 操作
因为性质 ，建立了虚边，而我们选择维护的却是实链，所以会导致根节点 (以下均称为 ) 到 的路径经过所有的边不一定全都是实边，即 到 的路径不通。
的意思为 将 到 的路径打通，也就是将 的路径上所有的经过的边都转化为实边。
这是 最核心的部分 (就属 的代码最长)。
这里以 大佬的博文 LCT总结——概念篇 中的例子予以说明。 他讲的特别详细，我不认为我能比他讲的还要详细。
有一棵树，假设一开始实边和虚边是这样划分的（虚线为虚边）
那么所构成的 可能会长这样（绿框中为一个 ，可能不会长这样，但只要满足中序遍历按深度递增（性质 ）就对结果无影响）
现在我们要 ，把 的路径拉起来变成一条 。
因为性质 ，该路径上其它链都要给这条链让路，也就是把每个点到该路径以外的实边变虚。
所以我们希望虚实边重新划分成这样。
然后怎么实现呢？
我们要一步步往上拉。
首先把 ，使之成为当前 中的根。
为了满足性质 ，原来 的重边要变轻。
因为按深度O在N的下面，在 中O在 的右子树中，所以直接单方面将 的右儿子置为 （认父不认子）
然后就变成了这样——
我们接着把 所属 的虚边指向的 （在原树上是 的父亲）也转到它所属 的根，。
原来在 下方的重边 要变轻（同样是将右儿子去掉）。
这时候 就可以变重了。因为 肯定是在 下方的（刚才 所属 指向了），所以I的右儿子置为 ，满足性质 。
然后就变成了这样——
指向 ，接着 ， 的右儿子置为 。
指向 ，接着 ， 的右儿子置为 。
的路径已经在一个 中了，大功告成！
代码其实很简单。。。。。。循环处理，只有四步——
归根到底，其实就是 ：
当 的右儿子为 的时候，我们就认为 是一条实边。
显然 是维护实链的，如果我们 是连通的，那么我们直接查询举行了。
同样的。如果不连通，那么就以为着我们需要将这一条链赋值成实链。我们按照上面图的模拟过程来即可。
模拟过程可以简化为 ：
- 旋转到当前 的根。
- 建立和父亲的实边关系。
- 更新节点维护的信息。
: 我们需不需要考虑当前和 这个点连接的实链，把他置换成虚边呢?
: 不需要，这个时候就体现出我们认父不认子的好处了，我们直接将 这个点的右儿子替换掉，就代表 这个点的右儿子已经处理完了。
qaq void Access(int u) {
for(qwq int y = 0 ; u ; u = f[y = u])
Splay(u) , ch[u][1] = y , pushup(u) ;
// 先旋转到当前 Splay 的根，然后通过 f[u] 建立的虚边找到父亲节点，同时将父亲节点
// 的右儿子赋为当前的这个点，形成实边，同时连接该节点和父亲所在的 Splay 。
// pushup 即为更新维护的信息
}
MakeRoot(x) 操作
就像他的意译一样， ，使成为根。缺宾语
那么如何操作呢 。我们上文已经知道了如何将打通一个点到根的路径了。
这时候用到 和 操作了。
我们这个 满足性质 , 所以 之后 ， 还是深度最大的点。
我们将其 旋转一下，本来它就是最大的，显然 在这个 中没有右子树。
于是我们翻转整个 ， 使得所有点的深度都倒过来， 没有了左子树，它成了深度最小的点，那 其实不就是树根了嘛。
qaq void MakeRoot(int u) {
Access(u) , Splay(u) , PushOver(u) ;
// PushOver(u) 就是翻转操作
}
FindRoot 操作
找树根 。
之后 不就是深度最大的点了嘛，我们就不断去找左子树左子树，也就是去寻找深度最小的点，当节点 没有左子树的时候，他的深度也就是最小的了，那么 就是树根了。
当然，其中有可能会有 标记，也就是区间翻转标记，我们这里直接下传即可，不下传无法保证 一定是树根。 解释的话，分析上一个操作。
qaq void FindRoot(int u) {
Access(u) ;
while(ch[u][0]) pushdown(u) , u = ch[u][0] ;
return u ;
}
Link 操作
在 中加入一条 的边。
让 成为树根 , 然后建立虚边。
这个地方需要特判一下，因为树上显然不能出现环，所以 ,这样才让 向 认父。如果不知为什么 向 认父，则建议重新审视一下 的模拟过程。
qaq void Link(int u , int v)
Split 操作
代表是抽出 这条路径成为实链。
这时候我们有 的启发，我们就可以直接让 成为树根。然后通过 打通 的路径即可。
qaq void Split(int u , int v) {
MakeRoot(u) , Access(v) , Splay(v) ;
}
Cut 操作
删除 这一条边。
如果题目保证断边合法，倒是很方便。
使 为根后 ， 的父亲一定会指向 , 且深度相差 , 当 之后，因为 深度小，所以 一定是 的左儿子。直接断开连接。
qaq void CUT(int u , int v) {
Split(u , v) ; f[u] = ch[v][0] = 0 ; pushup(v) ;
}
如果题目不保证断边合法，也就是不一定会存在该边。
那么我们也按照上面一样，去特判一下。首先使得 成为 的根，然后去判断一下 是否在一个子树内，如果不在，则不存在。接着去判断一下 的父亲是否是 ，如果不是，不存在，最后去判断一下 是否有左儿子，如果没有，也不行。
qaq void Cut(int u , int v)
Splay , Rorate，pushdown，其他操作
和普通平衡树很相似，但是有几处是不同的。
这里就直接给出代码了
qaq bool check(int x) {//判断节点是否为一个Splay的根（与普通Splay的区别1）
return ch[f[x]][1] == x || ch[f[x]][0] == x ;
}//原理很简单，如果连的是轻边，他的父亲的儿子里没有它
qaq bool jd(int x) {
return ch[f[x]][1] == x ;
}
qaq void PushOver(int u) {
swap(ch[u][1] , ch[u][0]) ;
tag[u] ^= 1 ;
}
qaq void pushdown(int u)
}
qaq void Rorate(int x)
qaq void Splay(int x)
pushup(x) ;
}
囊括了几乎上文所有内容 。
因为上文都说了，所以这里也是直接给出代码了。不过这个是早写的，所以用的是结构体存的，不过没什么两样
//
/*
Author : Zmonarch
Knowledge :
*/
#include <bits/stdc++.h>
#define int long long
#define inf 2147483647
#define qwq register
#define qaq inline
using namespace std ;
const int kmaxn = 1e6 + 10 ;
qaq int read()
while( isdigit(ch))
return x * f ;
}
int n , m ;
int f[kmaxn] , rt[kmaxn] , sum[kmaxn] , s[kmaxn];
struct SPLAY {
int val , sum ;
bool tag ; // 区间翻转的标记
int ch[2] ;
SPLAY() {
tag = ch[1] = ch[0] = 0 ;
}
}st[kmaxn << 1];
qaq bool check(int x) {
return (st[f[x]].ch[0] == x) || (st[f[x]].ch[1] == x) ;
}
qaq void pushup(int u) {
st[u].sum = st[u].val ^ st[st[u].ch[0]].sum ^ st[st[u].ch[1]].sum ;
}
qaq void Pushover(int u) {
swap(st[u].ch[1] , st[u].ch[0]) ;
st[u].tag ^= 1 ;
}
qaq void pushdown(int u)
}
qaq void Rorate(int x)
qaq void Splay(int x)
pushup(x) ;
}
qaq void Access(int u) {
for(qwq int y = 0 ; u ; y = u , u = f[u])
Splay(u) , st[u].ch[1] = y , pushup(u) ;
// 通过虚链指定父亲，将这个父亲旋转到当前父亲所在的 Splay 的根上，更新 u 这个点的右儿子。
}
qaq void MakeRoot(int u) { // 指定 u 为原树的根
Access(u) ; Splay(u) ; Pushover(u) ;
}
qaq int FindRoot(int u) {
Access(u) ; Splay(u) ;
while(st[u].ch[0]) pushdown(u) , u = st[u].ch[0] ;
Splay(u) ; return u ;
}
qaq void Split(int u , int v) { // 使得 u , v 这一条链能在一个 Splay 中
MakeRoot(u) ; Access(v) ; Splay(v) ;
// 先让 u 成为根，然后直接 Access 打通 v 到根
}
qaq void Link(int u , int v)
// 这是保证存在该边的情况
qaq void Cut(int u , int v) { // 断开 u - v 这条边
Split(u , v) ; f[u] = st[v].ch[1] = 0 ; pushup(u) ;
}
// 这是不保证存在该边的情况
qaq void Pre_Cut(int u , int v)
signed main()
return 0 ;
}
这里就是照搬 大佬的 LCT总结——应用篇（附题单）（LCT） 这篇博客了。
维护链信息（LCT上的平衡树操作）
P3690 【模板】Link Cut Tree
P3203 [HNOI2010]弹飞绵羊
P1501 [国家集训队]Tree II
P2486 [SDOI2011]染色
P4332 [SHOI2014]三叉神经树
动态维护连通性&双联通分量
P2147 [SDOI2008] 洞穴勘测
P3950 部落冲突
P2542 [AHOI2005]航线规划
BZOJ4998 星球联盟
BZOJ2959 长跑
维护边权（常用于维护生成树）
P4172 [WC2006]水管局长
UOJ274温暖会指引我们前行
P4180 [BJWC2010]严格次小生成树
P4234 最小差值生成树
P2387 [NOI2014] 魔法森林
维护子树信息
P4219 [BJOI2014]大融合
U19482 山村游历(Wander)
#3510. 首都
SP2939 QTREE5 – Query on a tree V
#558. 「Antileaf’s Round」我们的 CPU 遭到攻击
维护树上染色联通块
P2173 [ZJOI2012]网络
P3703 [SDOI2017]树点涂色
SP16549 QTREE6 – Query on a tree VI
SP16580 QTREE7 – Query on a tree VII
#3914. Jabby’s shadows
特殊题型
#207. 共价大爷游长沙
P3348 [ZJOI2016]大森林
P4338 [ZJOI2018]历史
#2289. 「THUWC 2017」在美妙的数学王国中畅游
LCT总结——概念篇
OI-Wiki — Link Cut Tree
LCT总结——应用篇（附题单）（LCT）
