动态树(Link-Cut-Tree)学习笔记

数据结构

Death is what gives life meaning.

初识LCT是高一下学期开学没多久，
当时的自己非常颓废，天天看小说，刷知乎，
导致那一段的知识点到现在非常薄弱。

还记得当时三位省队神仙给我们连着讲树剖，线段树，后缀数组，Ac自动机，LCT...头都大了

时至今日，必须要学会上述NOIP不怎么考的知识

正文:

动态树问题通常要求维护一个有根树森林，不仅支持树链剖分的链修改和查询，而且支持树的合并，分裂和更改树根的操作。（大部分情况下，动态树问题不要求子树查询和修改操作）
动态树和重链剖分类似，也需要维护树的轻重链信息，但是重链剖分所维护的树的结构是不会变化的，所以可以用线段树来维护，而动态树的操作则需要更加灵活的区间数据结构，一般通过平衡树实现。

因为动态树的形态会变化，所以按子树大小划分轻重儿子的方法是错误的。我们人为规定每次将访问的点到根的路径变成一条重链（与Splay思想类似，每次访问过一个点之后将其旋转至根），可以证明这样规定可以保证轻重儿子切换次数为均摊O(𝑙𝑜𝑔𝑛)次（证明见下文）。通过恰当的实现，Treap可以做到O(𝑛𝑙𝑜𝑔^2 𝑛)的复杂度，而Splay则可以做到O(𝑛𝑙𝑜𝑔𝑛)的复杂度

对于动态树来说，我们只用维护一个fa数组，如果一个节点是其所处Splay的根，那么其fa表示在树上与Splay所处重链上深度最小节点相连的父亲节点（因为Splay的根不一定是深度最小的节点，所以这个fa不一定与Splay的根相连），否则表示其在Splay中的父亲节点（由于Splay的深度序是中序遍历，所以这个节点与其fa也不一定相连）。