P3690 【模板】动态树（LCT）
P3690 【模板】动态树（LCT）闲话：
余既知 LCT ,后半日，吾志学之。时至机房，广查博客，或苦思冥想。怎料实力不济，铩羽而归。他人问之：“闻汝知 LCT ，且何谓 LCT 也”。其后半日，吾弃之，树坏不修。其后半年，余久摆烂无聊，乃复修LCT，其成稍进于前。然自后余多爱线段树，不常写。
blog 有 LCT 树，吾集训之年所首知也，今已亭亭如盖矣。
人话版：
暑假时第一次知道了 LCT 奈何蒟蒻太弱，三看题解而不懂。然后就搁置了大半年，然后在 2024/12/23 靠着神秘的题解之力 A 了这题，但还是一道 LCT 除模板以外的题都没写，直至今日，再战LCT,复修总结。
Solution:
首先是我最赞扬的一篇题解，要看图的话可以参考，这篇题解的图真的很好。
splay的部分这里先不过多叙述，我们先把它当成普通的splay就好。支持两种操作
[*]1 rotate :将某个节点上旋
[*]2 splay :将某个节点不断上旋，使其成为该平衡树的根。
首先我们明确一下，LCT 维护的是很多颗平衡树，每一颗平衡树对应的是一个联通块，平衡树上的键值是在原图上该节点的深度。
首先介绍一下最重要的操作：
access：
表示将当前节点x 到 x所在连通块(平衡树)的根root 这段路上的所有节点（在原树上）拿出来建一颗平衡树。
虽然说是“拿出来”，但是我们实际的操作是将从 x 开始不断跳父亲，让后将当前节点所对应平衡树节点 \(x\) 设为 其父亲 \(fa\) 的右儿子。我们思考为什么这么做是可行的，前面说到：平衡树上的键值是在原图上该节点的深度。所以在合并操作进行到 \(fa\) 时，并没有比深度更大的节点，所以 \(fa\) 的左儿子其实是空的。所以我们只要将之前合并好的连通块作为 \(fa\) 的右儿子就好了。这样就保证了在进行完 access 操作之后，\(x\) , \(root\) 在同一平衡树内并且这颗平衡树有且仅有 x->root 这跳路径上的所有节点。
形式化的： \(splay_x=\)\(y|y \in(x->root)\)
说了那么多，其实代码很简单：
void access(int x)
{
int y=0;
while(x)
{
//每次 splay 完，x 是没有左子树的，因为在目前合并出来的这颗 平衡树上，x 在原树中的深度最小。
//而它的右儿子又被我们强行赋为了 rt->x 这条链所形成的平衡树
//这样就保证了在 access 完了之后，这颗平衡树维护只存在 x->root 这段路径上的点
splay(x);rs=y;pushup(x);
y=x;x=fa;
}
}有了这个操作剩下的操作就好理解了。
make_root:
使得 x 成为当前平衡树的根。注意是成为而非上旋至。这两个操作有着本质上的区别。make_root会直接把它在原树上的深度直接赋为当前平衡树（连通块）内最小的，使得该节点在平衡树和原树上都是该平衡树（连通块）真正意义上的根。
听起来貌似挺麻烦的，但其实非常好写。
inline void rev(int x)
{
swap(t.ch,t.ch);
t.tag^=1;
}
void make_root(int x)//换根
{
access(x);splay(x);
rev(x);
}为什么可以这么写：因为在 access(x),splay(x) 执行完了之后 \(x\) 是根而且没有右子树。那么我们将 \(x\) rev了之后 \(x\) 就没有左子树了。也就是说，\(x\) 从该平衡树下最深的点变成最浅的点了，即该连通块的根。
剩下的操作都真·很简单了，说明都在注释代码里了。
int find(int x)//找到 x 所在的 平衡树/联通块的根 （动态的树，有可能是一个森林，所有节点的根并不统一）
{
access(x);splay(x);
while(ls)pushdown(x),x=ls;
splay(x);
return x;
}
void splite(int x,int y)//我也不知道这个函数为什么叫 splite 明明就是在把 x->y 这条路径找出来好吧
{
make_root(x);
access(y);splay(y);
}
void link(int x,int y)// 意义很明确的函数名称
{
make_root(x);
if(find(y)!=x)t.ff=y;
return ;
}
void cut(int x,int y)// 意义很明确的函数名称
{
make_root(x);
if(find(y)==x&&t.ff==x&&t.ch==0)
{
t.ff=t.ch=0;
pushup(x);
}
return ;
}这里再说一个细节：cut 的判断：
if(find(y)==x&&t.ff==x&&t.ch==0)第一个部分判的是 \(x,y\) 是否同属一个连通块，第二部分判的是 \(y\) 的父亲是否为 \(x\).
而第三个判断就很抽象了，我们思考他的意义是什么：
首先，\(x\) 只有右子树。所以 \(dep
页:
[1]