自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

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

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

以下是正文

• 原题链接

• 赛时想法，有问题欢迎提出。

考虑将这棵树以 $1$ 为根定形。为了方便表述，令 $cow(x)$,$now(x)$,$sum(x)$ 分别为以 $x$ 为根子树节点数，$x$ 节点干草捆数，以 $x$ 为根子树干草捆总数。

由于一定有解，所以最后每个节点干草捆平分，令其为 $aim$，即 $aim=\frac{sum(1)}{n}$。

自上而下考虑。首先一号节点没有父亲，此处的干草捆不够肯定就由儿子拿，多了肯定就往儿子拿。考虑它的一个儿子 $x$，有以下三种情况：

1. 若 $sum(x)=cow(x)\times aim$ ：这种情况下 $x$ 这棵子树自给自足，递归处理即可。

2. 若 $sum(x)>cow(x)\times aim$ ：这时 $x$ 这棵子树的干草捆数多了，于是在满足自己的需求下，多余部分全部堆到 $x$ 给父亲即可。

3. 若 $sum(x)<cow(x)\times aim$ ：此时父节点补给 $x$ 节点足够的干草捆，使其能够自足。

考虑到时时刻刻干草捆数必须非负，所以我们得到一个这样的策略：先递归处理所有情况一，二的 $x$，将多余的干草捆堆到 $x$ 结点处给父亲，然后从父亲向所有情况三的 $x$ 补干草捆，再递归处理。

于是自上而下，对每个节点的儿子分情况讨论，时时刻刻维护上面三个数组可。

此时还有一个问题是该方案的最优性，这可以通过对每一条边考虑来证明，读者自证不难。

代码