树上启发式合并小结

树上启发式合并（DSU on tree），可以概括为小的合并到大的上去（small to large¹）。

具体地说，设$F(u)$表示我们要求的结点$u$的信息，而$a_u$代表结点本身的数据。$F(u)$依赖于$u$子树内结点的数据，但这种数据并不能简单合并，需要挨个遍历以更新信息。不过这种数据具备可减性。

这时我们就可以考虑利用启发式合并来离线地计算每个结点$u$的$F(u)$。

考虑 DFS，我们先计算子结点的信息，在计算完后我们根据这个结点的身份决定是否让其父亲继承它的信息以及其子树的数据。如果继承，那么就保留其数据，否则就删除。

而身份判断的标准就是该结点是重儿子。所谓的重儿子指子树大小最大的儿子。

考虑将树重链剖分，那么可以发现结点$u$的数据会被遍历当且仅当我们正在计算$v$的信息，且

• $v$是$u$的祖先
• $u$在$v$的轻儿子的子树里

这等价于：$v$是$u$到根链上的重链的底端。

因此这样的$v$的个数是$O(\log n)$的。于是启发式合并的复杂度是$O(n\log n)$的。

CF600E

求子树众数和

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

代码

CF741D

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

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

代码

¹. https://codeforces.com/blog/entry/44351 ↩