[ABC345F] Many Lamps 题解

题意：给定一个 \(n\) 个点 \(m\) 条边的无向图，每个点的初始颜色为 \(0\)。一次操作是将一条边的两个端点的颜色翻转。求是否能通过若干次操作使得最终有 \(k\) 个颜色为 \(1\) 的点。

首先考虑什么情况下无解。会发现每一次操作，颜色为 \(1\) 的点的数量变化一定是 \([0,+2,-2]\) 中的一种，所以任何时候都一定是偶数。于是当 \(k\) 为奇数的时候，一定无解。

对于 \(k\) 不是奇数的情况，我们对于一个连通块进行考虑（可能有多个连通块，将贡献相加即可）。假设这个连通块有 \(x\) 个点，我们先求出这个连通块的一颗生成树，那么有一个结论：一定有一种操作方式使得这颗生成树中最终有 \(\lfloor \frac{x}{2} \rfloor \times 2\) 个颜色为 \(1\) 的点。因为对于树上的一个点 \(u\)，假设它下面的点的颜色已经全部为 \(1\) 了，那么一定通过控制 \(u \to fa_u\) 这条边的操作与否使得 \(u\) 这个点变为 \(1\)，所以除了根节点之外的所有点都一定能变为 \(1\)。而根节点能否变为 \(1\) 取决于 \(x\) 的奇偶性。

所以如果 \(\sum \lfloor \frac{x}{2} \rfloor \times 2 \ge k\) 的话，最终有解。对于每一个连通块可以通过一次 \(\text{dfs}\) 遍历得到具体的方案。否则无解。