P4429 [BJOI2018] 染色

题面传送门

这么牛的结论题！

分别考虑每个联通块，不断去掉一度点显然不影响，我们依次给出几个手玩的结论：

性质 1：如果有奇环，那么无解。

只需要给奇环上的集合全部赋值 \(\{0,1\}\) 即可。

性质 2：若存在两个环的边不相交，那么无解。

考虑一个环，取其对称的两个点，分别记为 \(p,q\)。

令 \(p\) 为 \(\{0,1\}\)，\(p\) 相邻的两个点分别为 \(\{0,2\},\{1,2\}\)，则这两个必有一个 \(2\)。然后除了 \(p,q\) 以及和 \(p\) 相邻的两个点全部赋值为 \(\{2,3\}\)，则 \(q\) 相邻的两个点有一个为 \(2\)。令 \(p\) 为 \(\{2,x\}\)，则 \(p\) 必定为 \(x\)。

考虑连接这两个环的某一条链，我们对两个环分别这样处理，使链连接的两个点的值固定为 \(x,y\)。

若这两个点之间有奇数个点，则令 \(x,y\) 不同，中间的点为 \(\{x,y\}\) 即无解。

若这两个点之间有偶数个点，则令 \(x,y\) 相同，中间的点为 \(\{x,z\}\)，\(z\) 取任意未出现的数即无解。

性质 3：若两个环相交的部分为奇数，则无解。

因为一条链上如果有 \(>1\) 个点则总是可以每次抵消两个点，所以我们不妨将这种情况看做存在 \((1,2),(2,3),(3,4),(1,4)\) 以及另外一个共用 \((1,4)\) 这条边的环。

令 \(1\) 为 \(\{0,1\}\)，令 \(2\) 与另一个和 \(1\) 相邻的点为 \(\{0,2\}\) 和 \(\{1,2\}\)，则这两个点必有一个 \(2\)，不妨令 \(2\) 的值为 \(2\)，\(3\) 的集合为 \(\{2,1\}\)，\(3\) 的值固定为 \(1\)，这样若 \(4\) 为 \(\{1,3\}\)，则无解。另一边也是对称的。

性质 4：若图不是广义串并联图，则无解。

性质 5：若图有两个三度点，且连接两个三度点之间的长度不为 \(2,2\) 加上一个偶数，则无解。

不想写了，反正我构造出来了。

然后有解的图就很简单了，容易判断。

submission