树上启发式合并小结

概述

树上启发式合并，可以简单概括为小的合并到大的上去。

Sack 传送门

要注意的是，删除的时候是直接删除所有信息的，不用考虑其他问题。

启发式合并的要点是，在处理子树$u$的时候，继承重儿子的信息。其他子树的信息都要加上来，然后还原。考虑复杂度。对于一个点$u$，只有在处理$u$的祖先的时候才有可能遍历到$u$。而只有在轻儿子上才会遍历到$u$。$u$到祖先有$O(\log_2n)$条链，因此有$O(\log_2n)$个轻儿子。因此复杂度是$O(n\log_2n)$的。

CF600E

求子树众数和

如果只考虑一棵树，可以$O(n)$求解。而本题信息是可以合并的，因此每次我们保留重儿子的信息（如果当前这棵树的根是一个重儿子就不清空）。这样每个结点的信息最多贡献$O(\log_2n)$次，总复杂度$O(n\log_2n)$。

代码

CF741D

求子树路径上字母任意顺序存在构成回文串的最长路径

由于是回文串，因此我们只关心出现次数的奇偶性。则设$c[mask]$表示出现状态为$mask$的结点的最大的深度。求经过当前根结点的最长路径，可以枚举子树结点，枚举某一位的出现次数为奇数或者出现次数都为偶数，然后更新当前答案。删除的话直接设为 -INF。显然可以保留重儿子信息。复杂度$O(n\log_2n)$。

代码