树上启发式合并

Summary

树上启发式合并离线统计每棵子树的信息。对每个节点，先递归它的各个轻儿子并在算完后清空这些贡献，再递归重儿子并保留其贡献，最后暴力把所有轻子树的贡献重新加入，就得到当前子树的答案。由于每个点到根的路径上轻边至多对数条，每个点只会被暴力加入对数次，总复杂度 O(nlogn)。它好写好用，是子树统计一类问题的常用工具。文末附一道统计子树颜色出现情况的例题。

参考资料

• 树上启发式合并 - OI Wiki

简介

树上启发式合并（DSU on tree）离线统计每棵子树的信息。对每个节点：先递归各 轻儿子 并在算完后清空其贡献，再递归 重儿子 并保留其贡献，最后暴力把所有轻子树的贡献加入，得到当前子树的答案。

由于每个点到根的路径上轻边至多 $O(\log n)$ 条，每个点只会被暴力加入 $O(\log n)$ 次，总复杂度 $O(n\log n)$。它好写好用，是子树统计类问题的利器。

例题

洛谷 CF600E Lomsat gelral

给定一棵以 $1$ 为根、$n$ 个点的树，每个点有一种颜色。对每个点，求其子树中出现次数最多的颜色之和（若多种颜色并列最多，则其编号全部计入）。