题解 P7148 【[USACO20DEC] Cowntagion S】

Unordered_OIer · 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