菜王的 blog

最后五分钟过掉成功翻盘，纪念一下。

首先发现，如果要最大化价值，所选出的 $k$ 个点一定在树上形成一个连通块。

证明过程考虑调整，如果不形成联通块，则一定可以找到一个点，将它向黑点最多的方向移动一条边（满足目标节点没有黑点），这样操作之后，其他边的价值不变，而这条边的价值增加了 $2$，而形成连通块之后，没有任何一个点可以这样调整。

而且，我们还发现，对于一个 $k$，如果一条边不在点形成的连通块内，则它的价值一定是 $k$，这样的边有 $(n - 1) - (k - 1) = n - k$ 条，所以这部分的贡献与树的形态无关，为 $k(n - k)$。

于是问题接下来就变成，对于每个 $k$，都求出一个连通块最大化它内部的价值。

我们先考虑对于一棵全是黑点的树，这个价值怎么简单的算。如果对于每条边模拟计算，这样的价值带绝对值不便维护，所以考虑对于价值做适当的变换去掉绝对值。

把树定根，这样，价值就变成 $\sum_{u \ne rt} |sz_u - (k - sz_u)|$，也就是 $\sum_{u \ne rt} |k - 2sz_u|$，我们发现，当 $sz_u > \frac k2$ 时，$(u, fa_u)$ 这条边的价值才是 $|2sz_u - k|$。于是取这棵树的任意一个重心为 $rt$，则价值就变成了 $\sum_{u \ne rt} k - 2sz_u$，即 $k(k - 1) - 2\sum_{u \ne rt} sz_u$。

这时，我们就可以换根树上背包来求后式（就是这个 $\sum_{u \ne rt} sz_u$）的最小值了（换根是因为要钦定根为重心），但是不好做也没必要。

考虑分别计算每个点 $v$ 对后式的贡献，则每个 $v$ 的祖先 $u$（包括 $v$ 自己）都会在后式当中统计到它一次，而这个统计的次数也就是 $v$ 的深度 $dep_v$（即 $rt \to v$ 经过的边数），所以后式等价于 $\sum_{v \ne rt} dep_v$（实际上 $dep_{rt} = 0$，所以 $v \ne rt$ 这个限制是没用的）。

得到这个式子，这道题也就做完了，因为重心实际上还有另外一个性质，也就是满足树上所有的点到它的距离之和最小，所以钦定非重心为根的答案一定不优。

通过这个性质，我们直接对每个根 $rt$ 算出选 $k$ 个点的答案并取最小值即可。

对于每个根算答案可以做到 $O(n)$，则时间复杂度为 $O(n^2)$。

code