动态树解析

## 基本概念 动态树中的每一个节点，它连向所有儿子的边中有一条实边和若干条虚边。实边和虚边实可以动态变化的，由实边构成的实链可以用splay来维护。 ## 支持的操作 1. 点或区间查询具有可加性和可减性的信息（可加性和可减性的定义参考线段树） 2. 动态加边或删边（LCT是为数不多的支持删除的数据结构之一） 3. 换根 4. split和merge（定义参考fhqtreap） ## 主要性质 1. 同一个splay中没有深度相同的节点 2. 实边在splay中而虚边连接两个不同的splay ## 各种主要操作 ### rotate 假设原来的树是这样的：  对p点rotate之后就是这样子的：  ### splay 把一个点一路rotate到根 ### access 把根和这个点上的路径全部变成实边，同时把一些实边变成虚边 就是把一个点splay到当前树的根节点，然后改右儿子，改轻重边 其实只有三件事： 1. 转到根 2. 换右儿子 3. 更新信息 ## 其他操作 ### isroot 它父节点的两个子节点有没有一个是自身 ### pushup&&pushdown 参考线段树 ### which 判断它是不是父节点的右儿子 ### getroot 先access再splay最后下传标记，左下角的那个就是root ### makeroot 先access在splay最后打标记 ### link 先makeroot再把一个的父节点设为另一个 ### split 先makeroot再acess最后splay ### cut 先split再改节点