【小记】dsu on tree 和树链剖分的一点结合

· · 算法·理论

前置知识:dsu on tree,重链剖分,长链剖分。

本文尝试找到这三个算法的一些联系。

观察传统 dsu on tree 的流程:

在处理一个点的信息的时候,是不需要额外访问它的重儿子的。

设处理子树 i 的代价为 w_i,那么全局的代价为:

\sum_{i}\sum_{j\in son(i),j\ne hson_i} w_j

于是 hson_i 应该选择 w 最大的儿子。

当然,一般来说,w_i 可以写作 s_i\times C,其中 s_i 为 i 子树的信息规模,C 为一次操作的复杂度,与具体的题目有关。下文全部提取出来一个 C,即将上式中的 w 换成 s。

接下来就是围绕 s_i 的两种不同定义与对应的求和上界展开。

当然,还有一种 dsu on tree 的写法是正常启发式合并,小的合并到大的,相比之下这一种与树联系更紧密,可以和树上的一些其它算法更好地结合。

最平凡地,s_i=siz_i,也是最经典的 dsu on tree。结合上面的过程,其实发现可以直接用重链剖分来理解,每一个点都只会在走轻边的时候贡献,直接用重剖可以分析出复杂为 O(Cn\log n)。

到这里似乎说了滚木新的东西。但基于这个东西,在一些特殊的信息上,可以查询 (x,y) 固定 x 的贡献最值:

形如 x,y 的贡献需要在 \operatorname{lca}(x,y)=z 处计算,且贡献可以被分离为只与 x;y,z 有关(其实就是 dsu on tree 的要求)。预处理,一个点暴力地将它的所有轻儿子加入到数据结构上。每次查询,给定 x,从它往上跳重链:

不难发现还可能扩展到支持单点修改,具体复杂度依需要的数据结构而定。

一个运用:qoj4924 蜘蛛上树。

而既然重剖可以,为什么不试一下长剖?假如 s_i=h_i,即 i 到叶子的最大长度,那么取 hson_i 为长儿子的话,复杂度就可以分析为 O(Cn)。原因是一条长链对规模总和的贡献只在于第一次跳轻边的时候。

练习:P17724 [SCP-S 2026] 路短最 / path。

长剖优化 dp 其实可以用这种方式来理解。所以一个最直接的想法就是类似 dsu on tree 的写法来写,维护一个 dp 数组,长儿子进入后不要撤销,直接加入当前节点的贡献后合并轻儿子。但这样写比较不优美,因为加入当前节点的贡献是一个偏移的过程,实现起来有点细节。

当然,如果加入一个节点需要全部改写 dp 的值而不是简单的偏移,长剖可能就无法胜任。

对于优美指针写法的理解:视作给每个点一个 dfn 值,长儿子优先,使得长链上 dfn 连续。给每一个点分配 [dfn_i,dfn_i+h_i-1] 的位置存储 dp 值;而 dfn_{hson_i}=dfn_i+1,h_{hson_i}=h_i-1,所以对应同一片存储空间。

我认为这个视角为长剖提供了一个好理解的角度。我终于理解长剖了吗

小练习:P14772 [ICPC 2024 Seoul R] Protecting Kingdom。题解。

为什么是小练习呢?因为这题相比于前两题就是小巫见大巫了。

用 gpt 的一句话来总结一下:保留哪个儿子,取决于实际需要合并的信息规模;复杂度证明的关键,则是这些未被保留的信息规模之和。

最后需要注意的一点:不要被毛毛虫火箭控制大脑!