CF2127H

sunkuangzheng · 2025-08-08 02:28:44 · 个人记录

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

证明：考虑一个同胚与 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)。