题解：AT_arc205_b [ARC205B] Triangle Toggle

· · 题解

总的黑边数量不好求，我们考虑从每个点连接的黑边数量角度来考虑。我们发现对一个三角形进行操作之后，一个点所连黑边数量的奇偶性是不变的，从而可以猜到一个结论：每个点所连黑边数量都可以达到与其同奇偶的可能最大值。

这个结论是正确的，我们考虑这样证明：如果有一个点所连黑边数量没有达到与其同奇偶的可能最大值，那么必定连了至少两条白边，我们考虑对该点和连的两条白边进行操作，可以发现其所连的两个点进行操作以后，所连黑边的个数不会减少，从而我们只需要一直进行这样的操作，就可以达到最理想的状态。

综上，我们只需要求出初始图的度数 d_i，答案即为 \frac{n(n-1)}2-\frac{1}2\sum\limits_{i=1}^n[d_i \equiv n \pmod 2]。