题解：CF2023E Tree of Life

水题解/se

首先有个比较显然的贪心，以 $1$ 为根，然后自底向上每个节点计算一下会向父亲延申多少边。当一个节点延申上去的边数量不足是可以多加几条。然后在 $1$ 处进行两两匹配即可。

这玩意正确性有问题。比如 $1$ 的两个儿子一个延申 $3$ 条边另一个延申 $1$ 条就不能两两匹配了。

解决这个问题也很简单，只要定度数最大的点为根。那么返回的边数大概就是不够根节点度数的，所以都要补边。也就不会出现绝对众数的情况。

时间复杂度：$\mathcal O(n)$。