夢に僕らで帆を張って
来るべき日のために夜を超え

标签 树上启发式合并 下的文章

October 27, 2019

CF600E Lomsat gelral

题意一棵树有$n$个结点,每个结点都是一种颜色,每个颜色有一个编号,求树中每个子树的颜色编号的众数的和数据范围:$1 \le n \le 10^5$题解算法: 树上启发式合并发现每计算一棵子树需要清空做下的标记,但最后一颗子树不用清空(显然选择重儿子)像树剖一样先处理出重儿子先计算轻儿子,再暴力清空(消除对其兄弟的影响)计算重儿子,不清空合并轻重儿子的值复杂度证明类似树剖,一个节点会被清空仅...