题解：CF2023E Tree of Life

Otomachi_Una_ · 2024-12-30 20:35:09 · 题解

水题解/se

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

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

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

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