题解 AT2304 【[AGC010C] Cleaning】

zhylj · 2020-04-07 14:17:12 · 题解

选取一个度数大于 1 的点为根（当然 n=2 的时候要特判一下），设 f_u 代表从某个点可以向上拓展的路径数量（显然叶子节点的 f_u 都为 a_u），设 s_u = \sum_{v\in u.{\operatorname {son}}} f_v，也就是从孩子能拓展上来的路径条数。

这些路径有两种情况：1. 合并成一个点；2. 继续往上拓展。

后者的数量显然为 f_u，前者的数量为 \dfrac {s_u-f_u}2 （每两条合并成一个）。

前者每两条可以清除一个石头，后者每一条可以清除一个石头，所以有：

就有：

可以发现这些都是定值，所以直接 DFS 一遍，判断每个 f_u 是否有 0\le f_u \le a_u，\max f_v 是否小于等于 a_u 即可。至于“\max f_v \le a_u ”这个条件是怎么来的，类似于这样一个问题：

有一个长度为 n 的正整数数列 a，每次取两个数 -1，试构造一个方案使得整个数列为 0 或说明不可行。

结论

**证明** 必要性显然。 充分性证明： - $n=2$ 的时候显然成立。 - $n > 2$ 的时候，不断进行操作，直到出现第一个 $0$ 为止，由于最大的数不超过总和的一半，此情况必然出现。由于 $n - 1$ 的情况成立，所以 $n$ 的时候成立，证毕。

不过需要注意的是，这两个问题的不同之处在于这个问题的“总和”会减去 f_u，即有：

就是上面所说的条件。