[数据结构与算法]树上启发式合并

[十二省联考 2019] 春节十二响

先证明引理：

1.划分集合越少越好（如果集合变多，答案一定比现有答案增大

2.最小集合数量为树的高度

然后根据这两条引理，就dfs遍历树，对每个节点维护个数组（代表集合最大值），需要维护两个操作

1.插入一个值（每次遍历到的节点）

2.将多个数组降序排序后按位取最大值

因为降序，数组用大根堆代替

最后根节点的数组每个元素为集合的最大值

每次操作时间复杂度都是和子树size的最大值有关，最后会变成n^2的时间复杂度

运用长链剖分的思想，每次遗传长儿子的堆，暴力合并其他的堆，与长链剖分一样，会让合并次数变为n次

这种运用遗传+暴力合并树上信息的方法叫做启发式合并

启发式合并

普通的启发式合并通常有两个特点

1.不支持修改

2.可以像莫队一样遍历一个节点后就及时更改答案

其实这种题大多数能用线段树合并来做，但是因为没有修改，考虑用更优的方法

求出重儿子后，主要分三个步骤

1.遍历轻儿子并求出轻儿子答案

2.求出重儿子答案并保存重儿子所留下的信息

3.暴力将轻儿子的信息加入，得到此节点的答案

每个节点被暴力遍历的次数是这个节点到根节点路径上重儿子的数量（重儿子暴力加）+1（第一次遍历此节点求出答案的时候），所以时间复杂度最坏O(nlogn）

如果此节点不是重儿子，要清空数组，就是把整棵子树全部减掉

CF600E Lomsat gelral

判断每个节点为根的子树中，颜色出现次数最多的编号和

按照启发式合并做即可,记录每种颜色的出现次数，记录答案和答案出现次数

CF246E Blood Cousins Return

维护的是每一层往下k个节点

直接记录的是层数和每个名字出现次数，对每一层的名字离散化，然后用指针动态分配内存即可