题解：AT_arc088_d [ARC088F] Christmas Tree

· · 题解

AT2983 评蓝的来了。

首先这个 A 的最小值是好求的。

你设一个 tag_u 表示以 u 为根的子树中，是否有从子树向上伸出去的链。

你递归算答案，对于一个儿子结点 v 如果没有从它子树向上伸出去的链，那么就多加一条链。

然后由于子树可以互相合并，所以你再减去合并的条数即儿子数量的一半。

现在来考虑此时 B 如何达到最小值。

直接找不太好找，发现有单调性所以直接考虑二分答案，问题转化为判断一个 B 是否能够满足在 A 条链以内覆盖整棵树。

设 f_u 表示从子树内伸上去的链的长度。

那么我们更新 f_u 的时候就需要找一个最小的 f_v 去更新 f_u ，并且剩下的儿子两两配对之后长度满足 len \le B 。

给儿子的 f_v 排序一遍之后这也有单调性，可以直接二分求答案。

总时间复杂度 O(n \log^2 n) 。

Code