【小记】dsu on tree 和树链剖分的一点结合
happy_zero · · 算法·理论
前置知识:dsu on tree,重链剖分,长链剖分。
本文尝试找到这三个算法的一些联系。
观察传统 dsu on tree 的流程:
- 访问所有轻儿子,在离开时撤销;
- 访问重儿子,保留信息;
- 再次遍历所有轻儿子,贡献答案并加入信息。
在处理一个点的信息的时候,是不需要额外访问它的重儿子的。
设处理子树
于是
当然,一般来说,
接下来就是围绕
当然,还有一种 dsu on tree 的写法是正常启发式合并,小的合并到大的,相比之下这一种与树联系更紧密,可以和树上的一些其它算法更好地结合。
最平凡地,
到这里似乎说了滚木新的东西。但基于这个东西,在一些特殊的信息上,可以查询
形如
- 查询
x 的子树。 - 在重链上,查询的是重链的一个前缀的信息,可以离线下来一起做或可持久化。
- 还可能跳
\log n 条轻边u\to v ,那么需要查的是v 扣掉u 子树的信息,这个在 dfn 序上是至多两段区间,可以直接查询。
不难发现还可能扩展到支持单点修改,具体复杂度依需要的数据结构而定。
一个运用:qoj4924 蜘蛛上树。
而既然重剖可以,为什么不试一下长剖?假如
练习:P17724 [SCP-S 2026] 路短最 / path。
长剖优化 dp 其实可以用这种方式来理解。所以一个最直接的想法就是类似 dsu on tree 的写法来写,维护一个 dp 数组,长儿子进入后不要撤销,直接加入当前节点的贡献后合并轻儿子。但这样写比较不优美,因为加入当前节点的贡献是一个偏移的过程,实现起来有点细节。
当然,如果加入一个节点需要全部改写 dp 的值而不是简单的偏移,长剖可能就无法胜任。
对于优美指针写法的理解:视作给每个点一个
我认为这个视角为长剖提供了一个好理解的角度。我终于理解长剖了吗
小练习:P14772 [ICPC 2024 Seoul R] Protecting Kingdom。题解。
为什么是小练习呢?因为这题相比于前两题就是小巫见大巫了。
用 gpt 的一句话来总结一下:保留哪个儿子,取决于实际需要合并的信息规模;复杂度证明的关键,则是这些未被保留的信息规模之和。
最后需要注意的一点:不要被毛毛虫火箭控制大脑!