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