动态树学习笔记
yiming564
·
·
个人记录
动态树
定义
动态树问题的定义为：维护一棵树，要求支持：
\text{LCT(Link Cut Tree)}
$\text{LCT}$ 把树划分为了若干条实链，每条用 $\text{Splay}$ 维护，其中，$\text{Splay}$ 节点的键值为该节点在原树中的深度。
### $\operatorname{access}
```cpp
```
$\operatorname{access}(u)$ 的功能是把 $u$ 到根的路径上的所有边全部变为实边，且与该链邻接的所有边都会变为虚边（包括 $u$ 的所有儿子）
其返回值为新生成的实链的根节点。
### $\operatorname{make\_root}