CF2127H

显然原图是广义串并联图，可以考虑按照广义串并联图一般做法解题。

证明：考虑一个同胚与 $K_4$ 的子图，取其中一个三度点，则会有三个三元环和三个四元环经过它，因此它已经包含在 $6$ 个环中，不满足要求。

设

f_{i,0/1/2,0/1/2}

表示边

i

两段的点已经选了

0/1/2

个度数时连通块内的答案，

g_{u,0/1/2}

表示点

u

选了

0/1/2

度数时对应的一度连通块内的答案，转移都是简单的。

复杂度

\mathcal O(m \log m)

。

文章操作