自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

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

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

以下是正文

P7148 题解

题意

给定一棵树，每次可以进行两个操作：

1. 选择一个节点，该节点的值翻倍。

2. 选择一个节点，使其均匀地将其值分给其所有的儿子。

问最少经过多少次操作可以将所有节点的值都 $\geq 1$。

题解

首先，对于每一个节点，如果它的感染者数目已经超过了儿子数，则进行的一定是儿子个数次 (2) 操作。

反之，如果在还没有足够的感染者个数的情况下就开始分，显然是不优的。

所以对于每一个节点都进行贪心：

• 如果还不够分，就执行若干次 (1) 操作，直到够分了为止。

• 如果已经够分了，就花若干天，每天执行一次 (2) 操作直到所有儿子都有感染者为止。

很容易证明这是最优的。

于是我们记录每一个节点的儿子个数，记为 $cson[u]$，每次 $dfs$ 到一个点，我们就先计算 $(\log cson[u])+1$，表示自增至足够感染者的天数（注意不是 $\text{ceil}$ ），然后进行分发，即花 $cson[u]$ 天给所有儿子都发一个感染者，最后注意根节点本身就有一只感染者，处理一下即可。

复杂度 $\mathcal O(n)$，期望得分 $100$ 分。

其实甚至可以不用 $dfs$，从 $1$ 枚举到 $n$ 然后对于每一个节点都单一决策也行。

UPDATE 2020/12/27 : 修改了一处笔误，求管理大大重新审核一下 qwq