自动搬运

查看原文

来自洛谷，原作者为

	_xinyu1113 **

搬运于2025-08-24 22:53:25，当前版本为作者最后更新于2023-12-21 11:36:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们充分发扬人类智慧：

记每个点的权值为 $\sum{\min(sz_v,k/2)\times[fa_v=u]}$，然后按权值从大往小排序。

根据数学直觉，在权值排序后，答案所取的根在数组中肯定比较靠前。

所以我们只取数组最前的 $20$ 个点来计算答案。

这样速度快得飞起，在 $1\le k \le n \le 5 \times 10^5$ 时都可以在 400ms 内卡过。