题解 - ARC210D Independent Set Game

更少的结论，更多的分析。我看搓 D 题还是难于直接爆 E 的。

简述题意

给定一 $n$ 点 $m$ 边无向图，A 和 B 两人轮流行动（A 先手）：

• A 选择一个没涂色的点，涂黑；
• B 选择一个没涂色的点，涂白。

A 获胜当且仅当黑点是独立集。判断最优策略下游戏的胜负。$n,m\le 2\times 10^5$。

约定和简单转化

可以理解为 A 每次必须删掉一个点的 1-邻域，B 每次可以删掉一个点，A 获胜当且仅当他可以执行 $\lceil \frac n2\rceil$ 次操作。

下文令 $P_k$ 表示 $k$ 个点的链，没有特别说明的时候默认指代一个极大连通块，孤点指的就是一个极大连通块同时是 $P_1$。$d_x$ 表示 $x$ 点的度数。

点数是奇数

A 是最后一个操作的人，发现 A 每次必须恰好删除一个点，要不然 B 只需要每次删掉某个没删过的点，A 就倒闭了。

只要场上有孤点，A 一定会抢，所以 B 为了让 A 无法操作，他也一定会抢。

• 孤点有偶数个；轮流拿完之后 A 没有孤点拿，必败；
• 孤点有奇数个：轮流拿完之后 B 选择一个点拿走，只要不产生新的孤点 A 就输了，所以 A 胜等价于剩余连通块都是 $P_2$。

总结一下：$n$ 是奇数的时候，A 获胜当且仅当图中只有 $P_1$ 或 $P_2$。

我们称这样的图是破碎的。

点数是偶数

B 是最后一个操作的人，A 至多允许有一步操作恰好删了两个点，那就必须是一个一度点和这个点的邻点，我们称这样的操作为奇异操作，下文用 $u,v$ 分别代称一度点和其邻点。如果图不是破碎的，那么 A 一定会做奇异操作。

同上的，如果有孤点，双方一定会抢。

孤点有偶数个

抢完孤点，现在剩余点数为偶，轮到 A 走，他只能走奇异操作。

这之后轮到 B 走，B 的策略仍然是先抢孤点，只要某个时刻场上没有孤点，且存在非 $P_2$ 的连通块，B 就可以在这个连通块上找一个非割点删去，然后 A 就必然失败了。

所以 A 奇异操作胜利的条件是操作后图是破碎的。换言之，所有 $P_3$ 子图都必须经过 $u$ 或 $v$，显然这里只提及 $v$ 也是对的。

刻画一下图的形态，除去所有的 $P_2$，图大概长得像：

总之就是，应该是有一些 $P_1,P_2$ 接在 $v$ 上面，接了 $1\sim 2$ 条边。

$d_v\ge 2$ 时，$\forall x\neq v, d_x\le 2$。$d_v=1$ 不可能，因为 $v$ 有一度点作为邻点而 $v$ 所在的连通块不是 $P_2$。

因此我们任选一个度数最大的点作为 $v$，删掉 $v$ 然后检查图是否破碎然后模拟即可。即可。

关于不用考虑 $u$ 的说明：如果 A 胜，由于所有拉出去的 $P_3$ 和三元环，除去 $v$ 以外剩下的两个点可以匹配，而总点数为偶，所以一定剩余至少一个和 $v$ 相邻的一度点，随便拿一个作为 $u$ 都没有关系。而且，不找这个 $u$ 也不会影响正确性。

总结一下：此时奇异操作已经被确定，令 $v$ 为度数最大的点，删去 $v$，判剩余的图是不是破碎的即可。

孤点有奇数个

抢完孤点，现在剩余点数为奇，轮到 B 走。A 必胜的条件是：无论 B 这一步删哪个点（下文称其为 $r$），A 都有一个能赢的奇异操作。

问题就在于：B 的操作，可能改变场上度数最大的点。

我们先约定 B 不会删一个 $P_2$ 里的点，这毫无意义。

……我们还有一点性质没用。

B 的操作对 $d_v$ 的影响不超过 $1$，所以如果存在 $d_v\ge 4$，合法的 $v$ 仍然不超过一个（$v$ 是必须被 A 删掉的，所以 $r=v$ 的选择会节省 A 的奇异操作，对 B 不优）。

然后就变成要判断剩下的图里，无论选什么 $r$，都不会存在 $P_3$，也就是说剩下的图是破碎的。考虑删完 $v$ 剩下的图点数得是偶数了，所以剩下的图刚好是一个 $P_3$ 其实是无理的。

解决了这个情形，然后就是 $\forall x, d_x \le 3$。然后 $v$ 只能从度数为 $3$ 的点里面选，我们称这些点是好点，有 $k$ 个。$k=1$ 的时候 $v$ 是唯一确定的，接下来讨论 $k\ge 2$。

记 $f_x$ 表示点 $x$ 的 1-邻域里好点的个数，如果存在 $f_x\le k-2$，那么令 $r=x$，剩下的备选好点就至少有 $2$，倒闭了。

否则

$$\forall x, f_x\ge k-1$$

又由于

$$\sum f_x=4k$$

考虑现在还有 $n'$ 个点时，得

$$4k\ge n'(k-1)$$

$$n'\le \frac{4k}{k-1}=4+\frac{4}{k-1}$$

$k\ge 2$ 时 $n'\le 8$，可以枚举 $p$。

总结一下：此时如果存在 $d_x\ge 4$，或者 $\{x|d_x\ge 3\}=1$，仍然令 $v$ 为度数最大的点，删掉它然后直接判剩余的图是不是破碎的。否则只有 $n'\le 8$ 时 A 可能必胜，枚举 $p$ 做同样的事情。

总结

对给定的图 $G=P_1\times c_1+P_2\times c_2+G'$，

• $G'$ 为空，A 必胜；
• $G$ 点数为偶且删去 $G'$ 中任意一个度数最大的点之后，$G'$ 是破碎的，A 必胜；
• $c_1$ 为奇且 $G'$ 点数是不超过 $8$ 的奇数的时候，若 $\forall p\in G'$，$G'$ 删去 $p$ 之后删去任意一个度数最大的点得到的图是破碎的，A 必胜；
• 否则，A 必败。

复杂度 $O(n+m)$，认为 $8$ 是常数。

AC link。