自动搬运

查看原文

来自洛谷，原作者为

	wukaichen888 复健 OI

搬运于2025-08-24 23:12:21，当前版本为作者最后更新于2025-08-18 16:19:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$O(2^{\frac{n}{2}}n)$ 做法。

考虑对于 $x$ 子树，求出包含 $x$ 的最优解。

先对 $x$ 子树剖 $x$ 所在的重链，对挂在重链上的轻子树全部暴力求解。钦定选取的 $x$ 重链前缀，将轻子树划分到两个集合，使得两个集合内总点数 $\le\frac{siz_x}{2}$，然后折半合并出最优解，这是经典问题。

考虑证明总能分两个合法集合。设重链长度为 $len$，构造一个序列 $a$ 表示所有挂在 $x$ 重链上的轻子树大小，然后往 $a$ 中加入 $len$ 个 $1$。将 $a$ 从大到小排序，试证明 $a_x\le\sum_{x\lt y}a_y$（可能有点不严谨）：在重链上找到最低的 $u$ 使得 $siz_u\lt x$，$siz_{par_u}\ge x$，$par_u$ 的轻子树 $siz\le siz_u\lt x$，选取 $par_u$ 子树内所有 $a$ 即可。然后从大到小依次考虑 $a$，由于 $a_x\le\sum_{x\lt y}a_y$ 且 $\sum a=siz_x$，所以你总是能将 $a_x$ 扔进较小的集合。

算完包含 $x$ 的最优解直接递归算所有子树即可。

复杂度 $\sum{2^{\frac{siz_x}{2}}siz_x^2}$ 即 $O(2^\frac{n}{2}n^2)$（因为有排序），能优化到 $O(2^\frac{n}{2}n)$，人傻常数大，跑得比 $O(2^{\frac{3n}{2}}n)$ 慢。