思路
我们设 f_u 表示以 u 为根的子树，需要深度为几的完全二叉树才能构成，那么最终的答案即为 f_1。既然题目给的是一颗有根树，我们自然想到通过儿子节点的 f 来求出当前节点的 f。我们考虑如果有两个儿子节点的 f 值为 0，那么我们可以把它们合并成一个需要深度为 1 的完全二叉树的节点；同样的，如果两个儿子节点的 f 值为 0 和 1，那么可以把它合并成一个需要深度为 2 的完全二叉树的节点。但我们考虑儿子节点 f 值为四个 0 的情况，如果我们按顺序一个一个合并的话深度为 3，但我们完全可以把四个 0 两两合并，最后再把两个 1 合并得到 2，这样显然更优。我们不难想到这样的贪心：每次选择两个最小的 f 值合并，直到只剩下一个 f 值，那么当前节点的答案即为这个 f。每个节点开一个优先队列即可做到 O(n \log n)。注意要特判只有一个儿子节点的情况，此时的 f 值为儿子节点的 f 值加 1。
代码
赛时代码