经典题：cf600E

题意 

(资料图)

已知树的每个结点有点权，表示颜色编号。对于树的每个结点，求它的子树中出现次数最多的颜色编号之和。树的结点数 1≤n≤10^5 。

分析

启发式合并就是每次总是将小的集合往大的集合合并。这样，一次合并的复杂度就是较小集合的大小。由于小的集合经过合并后，大小至少翻倍，因此一个点最多被合并log(n)次，总的时间复杂度上限是n*log(n). 我们维护一个集合数组se[u], 表示u的子树中出现次数最多的颜色标号集合，由于还要知道具体出现的次数，我们再维护一个map数组cnt[u], 表示u的子树中每种颜色出现的次数。每次我们递归u的子结点v, 将cnt[u]与cnt[v]中size小的那个往大的合并，同时更新se数组。

最近的比赛题：cf872div2E

题意

给定一棵树，每个点有点权。求至少需要修改多少结点的点权, 才能使得根结点到每个叶子的路径的异或和均为 0？

分析

设dp[u]是以u为根节点，使得u到子树内各叶子结点的异或和等于0的最少修改次数。se[u]是经过最少次数(dp[u])修改后，u子树中所有链上的异或和的可能取值。设v1, v2, ..., vk是u的子结点。显然，如果u是叶子，dp[u] = 1

否则，如何利用dp[v1], ..., dp[vk]更新dp[u]? 我们想到dp[u] += ∑(dp[vi]), 但这还不够，事实上，如果有多个子结点的se[vi]有交集，说明这些路径可以取到相同值，我们只要在u修改一次，就可以使得这些有交集的路径都变为0。

比如这颗子树中，有三个子结点是1，一个2，一个3，我们只要将u结点异或上1，就可以将三条通往权值为1的路径变为0，而值为2的结点异或上2再异或上1，值为3的结点异或上3再异或上1，这样少修改2次。我们猜测少修改的次数就是子结点值最多出现的次数-1。更一般的，本来在叶节点/子结点直接修改的步骤被挪到父结点修改，由于子结点有多个相同值，在父结点修改可以减少一些修改次数，减少的次数最多是子结点值最多出现次数-1。证明：只要证明不会有比这更优的情况即可：若u为根节点，则为图中的情况；否则，若不将u修改为出现最多的值，并且假设在之后的向上合并中有好处，即恰好等于0，这样在根节点会少合并一次，但在u子树中至少要多修改一次，因此将u修改为出现最多的值是最优的。

所以我们用启发式合并维护出现次数最多的值，即把se[u]与se[v]中size小的往大的合并。由于只有出现次数>=2时才能减少操作次数，因此se[u]中只保存出现次数最多且超过2次的值。最后，如果根节点的se中有0，就可以不再少修改一条路径。