solution-p9962

_xinyu1113 · 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 内卡过。