CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

======lct======
我说这是我本命数据结构有人信吗（

=====前置知识=====
请务必理解：\\
[[2020-2021:teams:no_morning_training:fayuanyu:pou|树剖]] \\
[[2020-2021:teams:no_morning_training:fayuanyu:splay|splay]]

参考论文：QTREE 解法的一些研究

=====原理=====
树剖维护重链，而lct维护实边。

我们令一个子树的树根 到 子树中最后访问的点的路径 是 **实边** \\
则最后一次访问的点，到树根的路径，全部为**实边** \\
每个点到它的儿子中的边最多有一条**实边**

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=====

CVBB ACM Team

用户工具

站点工具

页面工具