$LCT$维护子树信息学习笔记 (LCT)维护子树信息学习笔记

昨天(FDF)好题分享投了 ([ZJOI2018])历史这题。

然后我顺势学学这个姿势。

结果调了一年。。。于是写个笔记记录一下。

基本原理

比较显然地，虽然父子关系在不断变化，但是重链与重链之间的连接是不变的。换句话说，一个点的某个虚儿子也许并不是他在原树中的某个儿子，但是这个点总和上来的信息是这整棵子树的。

所以我们定义这个点总和的信息（记为(siz)）为总和该子树的所有信息，

然后记(fsz)为虚儿子的总和信息，(val)为单点信息。

那么可以得到信息的统计式为：

(siz[x]=siz[ls]+siz[rs]+fsz[x]+val[x])

若将(x)做(Splay)到根的话，则这个点的(siz)就是以这条重链链顶为根的子树的信息和。

（一定把原树和(LCT)分开啊

而如果我们要查以某个点为根的子树信息和的话，则先将其(Splay)到根，

那么所求即为：(siz[rs]+fsz[x]+val[x])

很简单，就是自己重儿子的所有信息加上自己的虚子树信息以及自己

这里(siz)的用处自己脑补一下，很显然这个信息用(siz)整合出来也是对的。

这就是最基本的做法了。

这个很好办，考虑虚实边的修改只会在一些情况下出现。

(Access:)直接做加减法维护(fsz)就行了。

(Link:)因为每次连边是连一条虚边，所以我们直接维护，要注意的是作为儿子的点要被(Splay)上来总和信息。

(Cut:)没有特别的地方，和上面一样做即可。

如果带修改，那么就意味着我们需要更新这个被修改点到原树树根的信息。

到树根？(Access!)

直接大力(Access)一波，每次跳一条虚边就直接做一次单点修改就行了，注意切换虚实边。

如果要求魔改(Access?)

那得好好研究一下它到底长啥样啊。

首先，(Access)中前一条重链那棵(Splay)的根不一定是你的原树中的那个儿子，你得一直沿着左儿子找，找到深度最小的那个才是。

这个找的复杂度应该与(Splay)的复杂度相当，所以不影响其复杂度。

然后呢，你想要那个儿子的子树信息怎么办？再(Splay)上去？

不用了，虽然前一条重链那棵(Splay)的根不一定是你的原树中的那个儿子，但是它确确实实总和了那棵子树的信息，所以直接调用它的信息即可。

想用(Access)模拟某种染色过程？

不就是有些边不能连吗？信息还是直接加加减减来维护，连边特判就行了。

那为什么历史那题要写这么久？

我菜。

所以这个还是比较简单的，毕竟目前没写到太喵的做法。

那么就这样了。