题解

思路

把白色记为 $1$，黑色记为 $2$。考虑当前还没有删除的树。若某个叶子是灰色，或它的颜色等于本轮选择的颜色，那么可以把它加入本轮操作。删除叶子不会把其余顶点分成多个连通块，因此在同一轮中，新出现的同类叶子也可以继续删除。

使用标准的交换论证可以得到下面的叶子规范化引理：存在一种最优方案，使每一轮都把当前能够连续剥掉的、属于本轮颜色或灰色的叶子全部删除。若某个最优方案没有删除这样的叶子，把这个叶子提前加入本轮不会破坏剩余树的连通性，也不会引入另一种非灰颜色；反复进行该调整即可。反过来，在这些叶子被剥完以后，所有剩余叶子都是另一种颜色，因此下一次非空操作必须使用另一种颜色。

于是，非灰颜色只能在 $1,2,1,2,\ldots$ 间交替。唯一的选择是第一轮从白色还是黑色开始，分别模拟后取较小值即可。

做法

维护每个尚未删除顶点的度数，并为三种颜色各维护一个队列。初始时把度数不超过 $1$ 的顶点加入对应队列。

固定第一轮颜色 cur 后：

1. 只要灰色队列或 cur 对应的队列非空，就取出一个顶点并删除；
2. 每删除一个顶点，令它仍未删除的邻点度数减一；若某邻点的度数刚好变为 $1$，把它加入对应颜色队列；
3. 两个可用队列均空时，本轮结束，答案加一，并令 cur = 3-cur；
4. 直到所有顶点都被删除。

每个顶点只入队、出队和删除一次，每条边只被访问常数次。分别以白色和黑色开始模拟，总复杂度仍为线性。

正确性证明

引理 1

在一轮使用颜色 $c$ 的操作中，可以把所有当前为叶子且颜色为 $0$ 或 $c$ 的顶点加入该操作，并继续加入删除后新出现的同类叶子，而不会使操作数增加。

证明。 当前剩余图仍是一棵连通树。删除叶子不会断开其余顶点，所以本轮随后选择的顶点仍处于同一连通块。加入的顶点只含颜色 $c$ 和灰色，不违反颜色限制。故把这些顶点提前到本轮删除是合法的，且不增加操作数。重复此过程即得结论。 $\square$

引理 2

一轮颜色 $c$ 的叶子被全部剥除后，如果树仍非空，则下一轮必须使用颜色 $3-c$。

证明。 此时没有颜色为 $0$ 或 $c$ 的叶子。任意非空树至少有一个叶子，因此剩余叶子全为颜色 $3-c$。由引理 1 可将其中一个这样的叶子放到下一次非空操作；该操作不能同时使用颜色 $c$，所以其非灰颜色必为 $3-c$。 $\square$

定理

算法输出删除整棵树所需的最少操作次数。

证明。 固定首轮颜色。引理 1 表明每轮贪心地剥除所有可用叶子不劣于任何最优方案；引理 2 表明只要还有顶点，下一轮颜色就被唯一确定为另一种颜色。因此模拟得到该首轮颜色下的最优操作数。所有方案的首轮非灰颜色只能是白色或黑色（全灰时两种模拟等价），取两者最小值即为全局最优值。 $\square$

子任务算法

• 子任务 1：所有顶点均为灰色，一次操作即可删除全部顶点。
• 子任务 2：对不超过 $12$ 个顶点的剩余集合做状态最短路，枚举单次操作删除的合法子集，复杂度 $O(3^n n)$。
• 子任务 3：每轮扫描所有顶点，反复寻找当前可删除叶子，复杂度 $O(n^2)$。
• 子任务 4：使用三个叶子队列，复杂度 $O(n)$。

复杂度

单个测试用例时间复杂度 $O(n)$，空间复杂度 $O(n)$；所有测试用例的总复杂度为 $O(\sum n)$。