前置芝士:Splay
LCT(Link-Cut Tree)
使用场景:动态树问题。
基本概念:
- 原树:给定的原始树。
- 实边:在原树中节点 \(cur\) 选取一个子节点 \(son\),则 \(cur-son\) 的连边为实边。
- 虚边:不是实边。
- 实链:由实边构成的链。
基本思想:
- 将原树中的一条链,用一颗平衡树(一般是 Splay)来维护,其中平衡树的中序遍历是原树中深度从浅到深的一条路径。
- 维护平衡树的森林,森林中的节点与原树中的节点一一对应。
- 一颗平衡树维护的是原树中的一条实链。
使用场景:动态树问题。
基本概念:
基本思想: