菜王的 blog

好题。

以下将操作一改为子树 $-1$，操作二改为链 $+1$，$a_i$ 取反。

两个操作之间是独立的，我们考虑先搞出只使用其中一种操作就能归零的一个条件，然后再用另外一种操作去达成这个条件。

那么显然只使用操作一就能归零的条件是 $\forall 2 \le i \le n, a_i \ge a_{fa_i}$ 且 $a_1 \ge 0$。

我们将这两个条件分开来看。操作二对第一个条件 $a_i \ge a_{fa_i}$ 的影响是给 $a_i - a_{fa_i}$ 减去一个非负整数，这是不优的；而其对第二个条件的影响是给 $a_1$ 加一，这是不劣的。

所以第一个条件如果初始不满足，那么一定无解。现在我们的目标就是在不违反第一个条件的情况下尽可能多的操作。

那么我们可以 dp，设 $f_u$ 表示 $u$ 子树内最大的操作次数，那么 $f_1 + a_1 \ge 0$ 是有解的充要条件。转移也是简单的，我们二分 $f_u$，则 $f_u$ 合法的条件是：

• $\sum_v \max(a_u + f_u - a_v, 0) \le f_u$；

• 若 $u$ 不是叶子，则 $f_u \le \sum_v f_v$。

正确性显然。那么这个题就做完了，总时间复杂度为 $O(\sum n \log v)$。

代码。