题解 P5649 Sone1
Link-Cut-Tree和Euler-Tour-Tree
-
在 【BZOJ3786】 星系探索中，我们使用了 splay 维护括号序列的数据结构，这样就能够完成子树的修改，我们考虑在他上面拓展。
-
括号序在右括号是否减去信息限制了我们对链或者子树的维护。
-
究其根本，ETT 和括号序在动态情况下难以对单独找出链信息主要瓶颈在于在合理的时间复杂度以内用区间表示出一条链。
-
我们令一个点第一次出现的点为代表节点，只有他会存储信息。
-
由于平衡树的性质，我们可以在
O(\log n) 的时间完成区间平移，这启发我们将静态的树链剖分维护改为 LCT 维护。 -
先考虑想要得到状态，即一个实链 splay 中的所有的节点组成的链能够在ETT上被方便的表示出来。那么为了得到这个结构，我们在 LCT 虚实儿子变换的时候将操作映射到 ETT 上。若y即将成为 x 的实儿子，那么我们就在 ETT 对应的将 y 所在实链的所有点的子树区间平移到 x 的右边，与 x 相邻，保证操作前后合法，那么完成操作后，y 到根的代表节点全都在整个 ETT 的最左侧。
-
换根也比较平凡，找到 x 的代表节点， access 它，然后
[1,rk_{x}],[rk_{x}+1,last] 分别翻转，至于正反翻反了的可以直接标记解决。 -
那么它就可以维护一颗动态树的链和子树的查询与修改操作了。
-
子树大小可以有LCT直接维护，故只需记录代表节点，且欧拉环游序，括号序，DFS 序，均可以实现。 LCT - ETT (卡常改了一个数组
-
紫色下划线是代表节点。
广告：其他解法，浅谈ETT