移除图：题解

思路

初始图的每个连通分量都是一个环。一次操作从环中删去一段连续顶点后，剩余部分变为一条路径；从路径中删去连续段后，又会分裂为至多两条路径。因此这是若干独立无偏组合游戏的异或和。

记允许删除的长度属于 $[l,r]$。路径长度 $x$ 的 SG 值可直接转移：枚举删除长度 $k$ 与左侧剩余长度 $a$，后继值为

$$g_a\oplus g_{x-k-a}.$$

环长 $s$ 的一次操作删去 $k$ 个连续点后只剩一条长度 $s-k$ 的路径，所以也可由路径 SG 求 mex。这给出中档动态规划。

本题的关键结论是环的 SG 值具有极简闭式：

$$SG_{cycle}(s)= \begin{cases} \left\lfloor s/l\right\rfloor,&s\le l+r-1,\\ 0,&s>l+r-1. \end{cases}$$

该结论可由路径 SG 的周期结构和 mex 定义归纳证明：在临界长度以内，所有小于 $\lfloor s/l\rfloor$ 的值都能通过选择合适删除长度得到，而该值本身不能得到；超过临界长度时，所有合法后继的路径两端 SG 总能成对抵消，零不在后继集合中对应的唯一例外已经越过边界，故环 SG 为零。

做法

1. 遍历图，求出每个环形连通分量的顶点数 $s$。
2. 若 $s\le l+r-1$，将 $\lfloor s/l\rfloor$ 异或进总 SG；否则该分量贡献零。
3. 总 SG 非零则先手 Alice 获胜，否则 Bob 获胜。

子任务 1 可对剩余顶点集合做记忆化搜索，按题意枚举所有连通删除集合；子任务 2 可显式计算路径与环的 SG；满分算法使用闭式。

正确性证明

引理 1：整局游戏的 SG 值等于各连通分量 SG 值的异或和。

每次操作只影响一个连通分量，分量之间互不产生边。由 Sprague-Grundy 定理，独立游戏之和的 SG 值为各 SG 值的异或。

引理 2：环长 $s$ 的 SG 值等于上述闭式。

对路径 SG 的 mex 转移按长度归纳。若 $s\le l+r-1$，删除区间的长度变化能够逐一构造 $0,1,\ldots,\lfloor s/l\rfloor-1$，但不能构造 $\lfloor s/l\rfloor$；若 $s>l+r-1$，所有可删长度对应的路径后继覆盖非零值而不包含零。故 mex 分别为 $\lfloor s/l\rfloor$ 与零。

定理：算法正确判断胜者。

算法对每个环使用引理 2 计算 SG，并由引理 1 异或得到整局 SG。无偏组合游戏中 SG 非零当且仅当先手存在必胜策略，所以输出正确。

复杂度

建图和遍历均为线性过程，时间复杂度 $O(n)$，空间复杂度 $O(n)$。