写给高二同学的
本文主要用于校内讲课，大部分资料来源与网络，如有侵权立删。
\text{Link Cut Tree}
\text{引入}
- 对于一棵树，要支持删边，加边，查询联通性三项操作（必须在线）。
\text{分析}
- 如果只有删边或者加边，可以离线。
根据套路，如果只有删边，或者加边。可以考虑将操作离线下来用并查集来维护。
- 如果可以离线。
仍然是把操作离线下来，考虑加边和删边的性质，一条边可以在时间轴上覆盖一段区间。这个因为要考虑撤销，可以用线段树分治来做。
- 考虑原问题。
删边，加边本来一起出现就不太好处理。考虑有没有什么高级的数据结构可以维护一棵树的动态联通性。
\text{前言\&概念}
-
-
动态树
\text{LCT(link cut tree)} 是一个可以动态维护森林上各种信息的东西(删除查找合并啥的都有吧)，原来的森林我们称为原森林，里面有实边和虚边，为啥有这两种边呢，首先\text{LCT} 是用很多个\text{Splay} 维护这个森林的信息，那么因为\text{Splay} 本来就是个二叉树，所以我们要将原森林”剖分”成很多个二叉树并且用\text{Splay} 来维护它，用实边连接起来的一棵树就是原森林中的一棵树，我们称它为原树。 -
这个
\text{Splay} 会有些特殊，它的关键字是节点在树里面的深度。这棵原树我们也不是直接用\text{Splay} 维护，而是按每个点在原树中的深度为优先级，将每个点以优先级的中序遍历丢到splay上。我们一般将原树所对应的\text{Splay} 称为辅助树，原森林就对应一个辅助树森林。\text{操作函数} \text{access(x)} 将
x 到根节点的路径上全部变成实边，并弃掉自己所有的儿子(变成虚边：认父不认子)(每一个父结点对于自己的每个子结点只有一条实边)。\text{splay(x)} 将
x 旋转到当前splay 的根节点。\text{makeroot(x)} 这个操作的意思是将
x 点变为原树的根节点。\text{findroot(x)} 找出
x 所在的原树的根结点。\text{link(x,y)} 将
x,y 联接。\text{cut(x,y)} 将
x,y 之间的边断开。\text{例题} QWQ