树上启发式合并

参考资料

• 树上启发式合并 - OI Wiki

简介

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

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

例题

洛谷 CF600E Lomsat gelral

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