动态树的基本概念

一 点睛

常见的操作有序列操作和树上操作。

1 序列操作

通常采用线段树或伸展树（Splay Tree，Splay 树）。

2 树上操作

通常采用树链剖分或动态树。

二 动态树

动态树是动态的，维护一个由若干无序的有根树组成的森林，支持对某个节点到根的路径操作，以及对某个节点的子树操作，还支持换根、加/减边、子树合并/分离等。以 RobertE.Tarjan 为首的科学家们提出了 Link-Cut Trees（LCT），LCT 是最常见的一种解决动态树问题的工具。

1 树链剖分

为轻重链剖分，节点到重儿子（子树节点数最多的儿子）之间的路径为重链，一般采用静态数据结构如线段树或树状数组维护重链，静态数据结构无法解决动态问题。

2 LCT 为虚实链剖分

虚实链是动态变化的，每个实链都由一棵伸展树维护，所有伸展树就像一个森林，由虚边连接在一起组成一棵 LCT。

三 LCT

一棵 LCT 有以下性质。

1 一个节点到其子节点最多有一个实边，其他均为虚边。

2 每棵伸展树都维护一条按原树深度严格递增的实链。

3 每个节点都被包含且仅被包含在一棵伸展树中。

四 示例

1 原树

假设一棵树划分虚实边后如下图所示，图中一共有 7 条实链：A-B-D、E、C-F-I-M、L-N、G、J、H-K。每条实链都由一棵伸展树维护，按照在原树中的节点深度有序。

2 LCT

将上述 7 条实链分别构建 7 棵伸展树，每棵伸展树的根都与该实链的父节点通过虚边连接起来，LCT 如下图所示。

伸展树之间的连接“认父不认子”，在原树中，实链 C-F-I-M 的父节点为 A。在 LCT 中，实链 C-F-I-M 构建的伸展树的根为 F，树根 F 向该链的父节点 A 连一条边，表示该链的父节点为 A，然而 A 在原树中的儿子并不是 F。实链 C-F-I-M 对应的伸展树是动态变化的，但其父节点是不变的。LCT之所以被称为动态树，是因为它具有动态变化性：

a LCT 中的虚实边是动态变化的。

b 伸展树也是动态变化的，可以随时旋转，只要满足原树中的节点深度有序即可。

无论如何虚实变换、旋转，所有节点的相对位置都不变。若原树节点 x -y 路径上没有节点 z ，则操作完以后，在 x -y 路径上也不可能出现 z。