自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:44:10，当前版本为作者最后更新于2022-12-05 22:05:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

算法 1

输出每个点子树大小。

显然对链是正确的，期望得分 11。

算法 2

$c=1$ 时，一种指数级做法是记每一个点没球/有正电球/有负电球，然后状压 dp。复杂度 $O(3^nn)$。

当然你也可以使用其他暴力做法。期望得分 27。结合算法 1 期望得分 38。

算法 3

结论：先手全扔正电球，后手尽量让球与目标位置的 LCA 靠上。

证明：

首先，一个容量为 $c$ 的点可以被替换成一条长度为 $c$ 的链。于是接下来只考虑容量为 $1$ 的情况。

考虑对任意树归纳。归纳边界：

• 任意树，目标点为根时成立。
• 大小为 1 的树，目标点是任意点时成立。

下假设对于任意大小 $\leq S$ 的树，目标点为任意点时成立。

考虑一棵大小为 $S+1$ 的树，不妨假设目标点在左侧，左侧在双方均执行最优策略时需要投下 $k$ 个球（也就是说，投下 $<k$ 个球时，无论球的电性，均无法达到目标；而由归纳假设，投下 $k$ 个正电球可以达到目标）。设右侧子树大小为 $s$。同样执行上述策略时，显然 A 投下 $\min\{2k,s+k\}$ 个球可达到目标。下证明 A 不能使用更少的球数达到这个目标。

考虑 A 依次投下的球。考虑分组：第一个球和第二个球为一组，第三个球和第四个球为一组，以此类推。不难发现，在两侧均不满且任意一组球的第一个球投下之前，根的两侧电荷一定平衡。从而 B 只能在两侧均不满时决策一组球中的第一个球。

分类讨论：

• 如果两个球电性相同，无论扔哪边都得往左边掉一个，所以先扔右边。
• 如果两个球电性不同，扔右边就都去右边，扔左边就都去左边，所以扔右边。

因此，只要两侧均不满，对于任意一组中的两个球，B 一定能够保证只有后投下的球落入左侧，或者都不落入左侧。因此 A 不能使用更少的球数达到这个目标。

于是 A 最优策略得证。

证明 A 最优策略后，B 实际上已经没有决策，且过程就是让球与目标位置的 LCA 靠上。于是得证。

有了这个结论以后，对于每一个点 $u$，答案可以向上递推：初始是子树大小 $a_u=S_u$，每次往上一个点，设另一个儿子的子树大小是 $S$，则 $a_u\leftarrow a_u+\min\{a_u,S\}$。

暴力递推，复杂度 $O(n^2)$，期望得分 100。