2020-2021:teams:no_morning_training:fayuanyu:lct
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:fayuanyu:lct [2020/05/15 23:41] 发源于 创建 |
2020-2021:teams:no_morning_training:fayuanyu:lct [2020/05/17 23:28] (当前版本) 发源于 |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| 我们令一个子树的树根 到 子树中最后访问的点的路径 是 **实边** \\ | 我们令一个子树的树根 到 子树中最后访问的点的路径 是 **实边** \\ | ||
| 则最后一次访问的点，到树根的路径，全部为**实边** \\ | 则最后一次访问的点，到树根的路径，全部为**实边** \\ | ||
| - | 每个点到它的儿子中的边最多有一条**实边** \\ | + | 每个点到它的儿子中的边最多有一条**实边** |
| + | splay有很好的性质：能够低代价的合并 / 拆分树 \\ | ||
| + | 我们对每一条实边用splay维护。splay内部以(原树)深度为key (并不用显式的维护) | ||
| + | ''fa[i]'' 维护 ''i'' 到 ''father[i]'' (原树上的) 的虚边 (实边的fa[i]随便) | ||
| + | =====access===== | ||
| + | 关键操作是 ''access(i)'' 代表访问点 ''i''，同时维护实边 \\ | ||
| + | - ''splay(i)''，把 ''i'' 转到根 | ||
| + | - 分离 ''i'' ( splay 中的)右子树，即：将 ''i'' 指向儿子的实边置为虚边 | ||
| + | - ''get_leftmost''， 找出 splay 中最高的点 ''u'' | ||
| + | - 将 ''fa[u]''的右子树分离 (同 1，2) (将原有的实边转为虚边) | ||
| + | - 将 当前 splay 与 ''fa[u]'' 所在 splay 合并 (将边 ''(fa[u],u)'' 置为实边) | ||
| + | - 重复以上操作，直到根 | ||
| + | |||
| + | =====makeroot===== | ||
| + | 换根操作 ''makeroot(i)'' | ||
| + | - ''access(i)'' | ||
| + | - 实际上，只有路径 ''(root,i)'' 上的父子关系发生了改变 | ||
| + | - 那么，只要区间翻转 splay 就可以了 | ||
| + | |||
| + | |||
| + | =====cut===== | ||
2020-2021/teams/no_morning_training/fayuanyu/lct.1589557266.txt.gz · 最后更改: 2020/05/15 23:41 由 发源于
