常见 LCT 的不详细揭秘。

Luciylove · 2024-11-15 10:08:26 · 算法·理论

博主并不擅长动态树相关知识，所以只会总结一点常见的模型，考虑到习题各有风采，所以就不一一给出题解。

下文并没有震撼人心的 Massive Problem，请放心观看。

维护子树信息

LCT 并不擅长维护子树信息，不代表不可以维护子树信息，事实上是只需要额外的数据结构就可以做一些对虚子树信息的简单维护。

换根，子树加，子树和。

考虑对于虚子树和实子树分别维护标记，但是切换的时候如何维护真实的值呢？

考虑费用提前计算，提前减去来自标记的 \Delta，这样切换的时候就不会有问题了。

换根，子树最小值。

注意到最小值只可以使用可删除数据结构维护，每次使用 multiset 来维护最小值即可。

和上面类似，实际上是 LCT 维护对称信息的体现。

注意维护左端到右边某个点的最大值和右端到左边的最大值即可。

习题：

常见的模型是对点到根进行染色，这个和 access 是一样的。

但是维护路径颜色段均摊是很吃力的。

这个答案是虚树边长和 + 1，尝试拆分贡献。

具体想法是维护那些要算上的点：加上子树内有关键点的点、减去虚树的根的所有祖先。

你考虑扫描线 r，然后我们每一次直接 access 维护该点子树内的最近时间戳，然后每次只需要加入/删除一段祖先后代链的颜色段信息，使用任意黑盒均可。

注意到操作类似于 access，而切换儿子类似于虚实链的切换。

我们这样可以离线成若干个问题，有 n \log n 个区间 [l, r] 表示要在 [l, r] 时间内被操作，求操作方法使得不合法情况出现最晚。

直接左端点扫描线，然后每次取出右端点最小的那个就好了。

习题：

LCT 数生成树的技术引入题。

联通块个数显然就是点数 - 边数。

考虑用 LCT 来扫描线，然后维护编号的最大生成树。这样我们可以求出一条边存在的时间 [i, del_i] ，转化为求解这条边存不存在即可，使用在线二位数点解决即可。

考虑维护左端点 l 的最大可以扩张到的右端点 r，使得不存在环，不难使用 LCT 维护连通性问题。

那么就是数 [l, r] 内有多少个区间 [l, i] 满足区间的点在四连通性的情况下数一棵树。

考虑对于树这种特殊形态使用森林经典结论 V - E = 1。

那么我们就可以计算在左端点为 l 的情况下，每个点连了多少条边，注意到这个是对一个后缀的区间产生贡献。

那么我们可以使用线段树维护区间加来维护 V - E，利用最小值个数计算即可。

这个东西显然是可以右端点扫描线的。

维护到没有环或者所有度数大于 2 的点全部在环上即可，可以通过 LCT 维护环上 deg > 2 的点的个数，不难进行维护，一种实现代码的想法是尝试维护成环的位置和那一条链的信息。

你尝试加入这条边，维护左端点 l 使得 [l, r] 恰好只有一个简单环，这个是基环树就是 |V| = |E|。

这个东西就是线段树历史最小值个数和即可即可，时间复杂度是 O((n + q) \log n)。

习题：