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

这道题的方案限制是在树上做出的，所以我们不免会想到对子树考虑是否可以设计状态使其具有最优子结构，并且便于转移。

发现这些限制在儿子向父亲转移时具有极良好的性质：

• 根和子树内其它节点不在同一块中，单独成块。
• 以两个儿子为根的子树合并时，两边各取一个互不冲突的集合，并起来亦不冲突。

那么下面贪心合并的方案是显然的：两个子树分别按照段内最大值（即该段贡献）从小到大排序，然后两个子树一一对应合并，分段较多的子树剩下的段不合并。

还需要证明最优子结构性，即在儿子子树的最优方案中被分到同一段的元素，父亲处被分到同一段一定不劣。

我们用某个方案中所有段的大小升序排序后得到的序列代表它。如果两个方案 $a,b$ 满足对于任意位置 $i$ 都有 $a_i\le b_i$，我们称方案 $a$“严格不劣于”$b$。不难发现这样的关系构成了偏序，我们证明同一个子树内所有方案构成的偏序集的极小值是唯一的。

叶子节点本身构成的子树只有一种方案，所以极小值唯一；两种极小值唯一的偏序集按照上述方法进行合并，如果 $x$ 严格不劣于 $a$，$y$ 严格不劣于 $b$，并且 $x\not=a$ 或 $y\not=b$，那么显然 $x,a$ 合并后严格不劣于 $y,b$，并且两者不相等。