题目

在一个 $n$ 个点的树上玩井字棋,白先手黑后手,谁先拥有一个相同颜色的长度为三的简单路径则赢。初始有一些点已经被染白。

求是否先手必胜 / 后手必胜 / 必平。

$1\le n\le 5\times 10^5$.

分析

(图片均来自 CF 题解)

我们可以把已染白的节点作如下替换:

那么,若 $A$ 被染白,则后手必然要染 $B$(否则后手就输了),然后先后手都不会去染 $C,D$ 了。

然后此时仍然是白先手,但 $A$ 已经被染白了。

然后我们只需要解决没有染色的问题了,考虑若一个节点 $u$ 满足 $\deg_u \ge 4$,那么先手可以先染这个节点,那么后手是永远堵不上的,所以先手必胜。

同样的,若存在 $u$ 使得 $\deg_u = 3$ 且 $u$ 有超过 $2$ 个非叶节点作为相邻的点,那么先手必胜(先手先染 $u$,再染一个相邻的非叶节点)。

那么,情况就只剩下一条链,只有两端可能出现度数为 $3$ 的节点:

容易发现,若此时度数为 $3$ 的节点个数小于 $2$,则必平,否则考虑链上节点个数的奇偶性:若中间有奇数个节点,那么我们每次可以在距离端点奇数的地方染色,然后最后就剩下如下图二的情况,先手必胜。否则容易证明必平。

然后就做完了,时间复杂度 $\mathcal O(n)$.

最后修改:2021 年 07 月 21 日 11 : 42 AM