CF1827D 题解

EuphoricStar · 2023-05-16 18:44:43 · 题解

考虑固定一个重心，设 k 为重心最大子树大小，答案为 n - 2k。构造方法是往最大的子树塞叶子。

树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为 x，往儿子 u 的子树中加叶子。

• 如果 sz_u > \left\lfloor\frac{n}{2}\right\rfloor，那么 sz_u - 1 = \left\lfloor\frac{n}{2}\right\rfloor，并且 x 的其他子树大小 < \left\lfloor\frac{n}{2}\right\rfloor，那么 x 会下移到 u；
• 否则无事发生。

考虑树状数组维护每个点子树的大小，当前重心和当前的 k。只用考虑下移一条边的情况，因此是容易维护的。时间复杂度 O(n \log n)。

code