Problem Link
题目大意
定义树上一次操作为删除 u 节点，并连接 u 的父亲和 u 的儿子。给定一棵树，求一棵满二叉树能操作成该树的最小满二叉树深度。
思路分析
树形 dp。设 f_u 为以 u 子树还原成满二叉树的最小满二叉树深度。
可以发现合法性只和 u 子树的叶子结点个数有关，具体地，单对 u 来说，设其子树的叶子结点数为 k，则 f_u=\lceil\log_2k\rceil，结论显然。
因为所有儿子 v 都需要满足该式，且 u 只能有两个子树，因此 f_u 的大小由 f_v 直接决定。考虑从下向上转移 f，每次贪心合并最小的两个 f_v， f_{new}=\max(f_{v_1},f_{v_2})+1，直到合并剩下不超过两个子树，f_u=\max (f_{lson},f_{rson})+1。
Submission