Warning: session_start(): open(/tmp/sess_ee11a33f1b9e177c6dae163d7e664946, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
======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=====