[CF2031E] Penchick and Chloe's Trees 题解

感谢此题送我上 M。我喜欢你。

解题思路

正难则反。

考虑原操作的逆操作：选中一个节点以及其若干儿子，创造一个新节点，将这些儿子的父亲设为该节点，然后将该节点的父亲设为该节点。

容易发现，存在一种方案对原树使用若干次这种操作之后将其变为一棵二叉树，并且在所有由其生成的二叉树中深度最小的一颗的深度即为使用正向操作能生成原树的满二叉树的最小深度，并且可以证明在这种意义下逆操作仅选择两个点一定最优。

考虑如何得到这个深度：注意到其具有局部最优性，考虑树形 DP。

具体的，记 f_x 表示仅对 x 子树内的节点操作将其变为一颗二叉树时的最小深度。

转移时，将 x 的所有儿子的 f 值列为一个数列，转移形如每次从该数列中选择两个数 x,y 删去并将 \max(x,y)+1 加入该数列（即模拟计算使用逆操作合并这两个子树产生一个新的子树）直到只剩一个数，这个数即为 f_x。

要使得这个数最小考虑贪心：将数列中的数加入小根堆中，每次取其最小的两个进行合并，考虑到小的数要尽可能被多合并，可以发现这么做一定最优。