什么是动态树？
动态维护⼀个森林，动态的⽀持 \(2\) 个操作——添加边、删除边的数据结构。
它还可以维护树上路径的⼀些信息
时间复杂度单独操作：\(logn\)
虽然树连剖分的复杂度比动态树大，但是常数比动态树⼩。
回忆⼀下，树连剖分是维护一些重链来维护⼀些树，动态树也是类似的。
树链剖分可以将边分为重边和虚边，动态树可以维护实边和虚边。
具体这样表述:任意⼀个点最多只有一条实边
我们可以定义一条与实边对应的路径
如下图所示：
孤⽴点我们也单独当作实边处理
\(Spaly\) 维护的所有实边路径
红圈圈出来的就是一个 \(splay\)
Q： 具体怎么维护？
A： \(splay\) 中序遍历就是这个路径从上到下的遍历
\(splay\) 维护的是当前联通的所有实边的极⼤路径。
\(splay\) 通过其中的后继与前驱关系，来维护原树中的⽗⼦关系。
Q： 树跟树之间的关系如何维护？
A：\(splay\)中，\(rt\) 的\(fa\)信息还没利⽤上，所以⽤ \(splay\) 中 \(rt\) 的结点来维护
提示，\(x\) 的⽗节点不⼀定是 \(y\)，因为 \(x\) 不⼀定是 \(spaly\) 中的 \(rt\)
举个例⼦，假设 \(x\) 的 \(fa\) 是整个 \(splay\) 的 \(rt\)，那么\(t[r].p = y\)
Q：如何判断实边虚边？
A：因为每个结点最多只有⼀个实边
如果是虚边
在链接 \(splay\) 的时候只有只有这个 \(splay\) 的 \(rt\) 的 \(fa\)（点A）指向了某个点（点B）
但是这个点B的儿子却不是点A
虚边：子结点知道父结点是谁，但是父结点不知道⼦结点是谁
实边：⽗⼦之间相互知道
基于这种情况，我们只需要修改一次父子关系
我们可以很轻松的完成实边和虚边的转换
即：只需要确定父亲的儿子是谁
LCT基本操作
换边操作
将结点 \(fa\) 的后继改为想要变成实边的那个点 \(x\)
注意，得把 \(fa\) 转到根节点
此时fa的右⼦树是空的（因为 \(fa\) 的序号最⼤）
然后把 \(x\) 点接到 \(fa\) 的右⼦树
access(x)
核⼼操作：将 \(rt\) 到 \(x\) 的路径全部变成实边
(建⽴⼀条 \(rt\) 到 \(x\) 的实边路径)
注意这个实边路径只能包含 \(rt\) 到 \(x\) 的实边路径
这个过程是从下往上做的
⾸先需要将 \(x\) 旋到当前实边的 \(rt\) 上
接下来希望将 \(x\) 与 \(y\) 的连边边成实边
因为 \(y\) 是最⼤的点，那么直接将 \(y\) 旋到 \(rt\) 上
此时 \(y\) 没有右⼦树，直接将 \(x\) 接到 \(y\) 的后继节点上
那么直接将 \(x\) 插到 \(y\) 的右节点即可
此时，我们以 \(y\) 为 \(rt\) 的 \(splay\) 维护了整个路径
同样的道理对于 \(z\) 来讲，先把 \(z\) 旋转到 \(rt\)
此时 \(z\) 有左右子树（因为原树的有⼦树）
解决⽅案很简单
基于之前的换边理论，我们直接将y挂到z的右⼦树上
此时z就是这个 \(splay\) 的 \(rt\)
总结⼀下：节点直接旋上去。挂到右⼦树。递归做即可。
make_root(x)
将x变为根节点
利⽤第一个操作 \(access(x)\) 建立一条rt到x的实边路径。
对于一个无根树而言，我们将路径翻转是不会影响这个树的拓扑结构的。
所以直接将 \(x\) 转到 \(rt\)，然后将整个路径翻转即可。
拓扑结构不变：翻转前后 任意两点 \(x\) 到 \(y\) 经过的路径点不会发⽣变化。
路径翻转是 \(splay\) 的⼀个经典操作，直接将某个区间翻转即可。
利⽤ \(lazy-tag\) 实现。
提示：此处2个关系别搞混了，⼀个是从原树的，⼀个是 \(splay\) 的
⼀个疑惑：区间翻转后为什么不会破坏其他边的偏序关系
因为父子关系不会发⽣改变
find_root(x)
找到 \(x\) 所在的树的根节点
-
建⽴ \(x\) 到 \(rt\) 的实边路径（调⽤ \(access\)）
-
将 \(x\) 旋转到 \(rt\)
-
整个路径深度最小的点就是根节点
只需要找到整个树的最左的节点
做两遍 \(findrt\) 即可
进阶操作：判断 x 和 y 是否在同⼀个 splay 之中
split(x,y)
将从 \(x\) 到 \(y\) 的路径变为⼀条实边路径
⾸先通过 \(makert\) 将 \(x\) 变为 \(rt\)
再 \(access(y)\) 这样就实现了\(split\)
link(x,y)
如果 \(x\) \(y\) 不连通，则加\((x,y)\)这⼀条边
具体操作：
- 判断连通，\(makert(x)\) 将 \(x\) 变为 \(rt\)
看 \(findrt(y)\) 是否为 \(x\)
如果\(findrt(y)!=x\)
则说明他们不连通
- 由于在判断连通时\(x\) 已经是 \(rt\) 了
所以若需要加边，只需要将 \(x\) 的 \(fa\) 记为 \(y\)
cut(x,y)
若 \(x\) \(y\) 有边，则删掉该边
操作：
-
将 \(x\) 变为 \(rt\)
-
\(findrt(y)\) 找到y所在的根节点
-
考虑第⼆个操作的副作⽤：当 \(findrt(y)\) 后，除了找到y的根节点外的同时，会将y所在
树的 \(rt\) 旋转到 \(y\) 所在实边 \(splay\) 的 \(rt\) 上（在 \(findrt\) 后，会从左⼀直⾛找到 \(rt\)，然后 \(splay\) 操作为了保证时间复杂度，最后还会 \(splay\) ⼀次把 \(rt\) 旋上去。）\(y\) 所在实边\(splay\) 的根节点就应该是整个树的根节点，也就是 \(x\)。 -
如果\(x\space y\)有边，则意味着 \(y\) 应是 \(x\) 的后继。所以只需要判断 \(y\) 是否为 \(x\) 的后继即可（ \(y\) 是否为 \(x\) 的后继的判断标准：\(y\) 是不是 \(x\) 的右⼦树，同时 \(y\) 的左⼦树是否为空。
标签：rt,实边,LCT,Cut,int,Tree,splay,ch,节点 From： https://www.cnblogs.com/Aurora1217/p/17080643.html
这样就