AT_agc004_f 题解
_Z_F_R_
·
·
题解
更好的阅读体验？
感谢 @Oier_szc 的建议。
以下将把某个点的颜色变为相反的颜色，称之为把颜色取反。
1 树
先看树的部分分，直接做不那么直观，因为树是二分图，可以考虑把树黑白染色，还是看官解里的图：
这是转化之前样例一的染色方案。
这是转化之后样例一的染色方案。简单来说，就是按二分图的染色方式，将二分图被染成黑点的点的初始颜色取反，变成黑色，这样目标状态中，二分图被染成黑点的点的颜色也应被取反，变成白色。此时，限制条件由“两个点颜色相同”，变成了“两个点颜色不同”，由于条件的转换，我们可以把“将两点颜色取反”，变为“交换两点的颜色”。
梳理一下转化后的题意：
- 给定一个被二分图染色后的树，每次可以交换一条边两个不同颜色的点的颜色，使得最终的树是原树中所有点的颜色被取反后形成的树，求最小操作次数。
现在我们就可以直接得到，一棵树无解的充要条件是：将这棵树二分图黑白染色后，黑白点个数不相等。
进一步的，考虑对于一棵子树，假设其白点数量为 a，黑点数量为 b，那么，因为其目标状态为，其白点数量为 b，黑点数量为 a，且一次操作最多可以是黑点与白点的差加 2 或减 2，因此，发生在这棵子树的根连向其父亲的边上的交换操作至少为 |a - b| 次。
因此答案的下界为一棵树所有子树的黑白点数量之差，我们来大致证明一下操作数能达到这个下界。
我们考虑对于一条边 e = (u, v)，如下图所示：
假设 u 点一侧的子树与 v 点一侧的子树，均满足黑白点数量已经与目标的黑白点数量相同，我们称此时边 e 处于平衡状态。
如果黑色的 A 点要按红色路径转移到白色的 B 点，因为这样打破了边 e 的平衡状态，必然存在黑色的 C 点要按蓝色路径转移到白色的 D 点。
那么这样显然劣于黑色的 A 点按黄色路径转移到白色的 D 点，黑色的 C 点按绿色路径转移到白色的 B 点。
所以，我们得到结论，若 e 处于平衡状态，那么可以直接断开 e，将原树划分成两颗子树，递归的解决问题，因此，这种处于平衡状态的边对答案没有影响。
再考虑不处于平衡状态的边，我们发现，对于一个边 e = (u, v) 上的交换操作，假设 u 侧缺黑点，v 侧多出了一些黑点。那么只有将黑点从 v 点转移到 u 才是不劣的，因此我们可以尝试对每一条边定向，表示黑点怎样转移才是优的，如下图所示（用双向边表示处于平衡状态的边）。
我们若想达到操作次数的下界，那么一定是将黑点向箭头方向移动，直到所有边都是平衡状态。
但是，假设出现了以下两种情况（B, C, D, ... 处表示的是一棵子树，而不是一个结点）：
$A$ 处为黑点，且以 $A$ 点为端点的边都指向 $A$ 点，那么从 $B, C, D, ...$ 处的黑点就转移不到其他地方了（相当于 $A$ 处的黑点把路“堵住”了）。
这样看起来都达不到下界，但是我们可以证明两种情况均是不存在的。
> 证明：第一种情况中 $B, C, D, ...$ 处都缺黑点，即黑点个数小于白点个数，而 $A$ 点为白点，如果它的目标状态是黑点，那它也可以视为缺黑点，反之它不缺点，所以整棵树缺黑点，即黑点个数小于白点个数，无解，第二种情况同理。
通过以上结论，我们可以发现，边被定向后，整棵树大致构成一个 DAG，且 DAG 的若干个源点处一定是黑点，汇点处一定是白点，所以黑点只要沿 DAG 的方向流动，操作数一定能达到下界。
因此，我们大致证明了，总存在一种合法的方案使得答案能达到下界。
对每条边进行计数即可，具体实现中，可以将黑点权值设为 $1$，白点权值设为 $-1$，再统计每个子树权值和的绝对值之和。
## 2 基环树且环为偶环
注意到图仍是二分图。所以这种情况下无解的情况与树相同。
通过上面的结论，我们也可以把所有不在环上的边定向，同时，我们对环上的点赋一个权值 $val$，表示将黑点权值设为 $1$，白点权值设为 $-1$，该子树所有结点权值和。
如果对树的做法理解透彻，你会发现每个子树的权值和，其实是由子树的根结点连向其父亲结点的边的有向权值。
这里“有向”的意思是，由子树的根结点的父亲结点连向它本身的边的有向权值，是由子树的根结点连向其父亲结点的边的有向权值的相反数，具体的，我们可以定义，由 $u$ 连向 $v$ 的有向权值 $val$，表示必须要由 $u$ 向 $v$ 输送 $val$ 个黑点（$val > 0$），或是必须要由 $v$ 向 $u$ 输送 $-val$ 个黑点（$val < 0$），才能使这条边达到平衡状态。
这样，我们可以假设，环上的点依次是 $p_1, p_2, \dots, p_k$，$p_i$ 的权值为 $a_i$，由 $p_i$ 连向 $p_{i \bmod k + 1}$ 的边的有向权值为 $y_i$。
这样，我们可以得到：
$$a_i + y_{(i - 2 + k) \bmod k + 1} - y_i = 0.$$
令 $x_i = -y_{(i - 2 + k) \bmod k + 1}$，得到：
$$a_i - x_i + x_{i + 1} = 0$$
也即：
$$\begin{cases}
x_1 - x_2 = a_1 \\
x_2 - x_3 = a_2 \\
\cdots \\
x_k - x_1 = a_k
\end{cases}$$
显然这个方程没有唯一解（例如，可以令 $x_i' = x_i + t$ 得到一组新解）。
我们的目标是最小化 $\sum_{i = 1}^k |x_i|$。注意到：
$$
\begin{cases}
x_1 = x_1 - 0 \\
x_2 = x_1 - a_1 \\
x_3 = x_2 - a_1 = x_1 - (a_1 + a_2) \\
\cdots \\
x_k = x_1 - \sum_{i = 1}^{k - 1} a_i
\end{cases}
$$
因此：
$$\sum_{i = 1}^k |x_i| = \sum_{i = 0}^{k - 1}
|x_1 - \sum_{j = 1}^i a_j|$$
问题转化为，在数轴上标出 $0$，$a_1$，$a_1 + a_2$，$\sum_{i = 0}^{k - 1} a_i$ 这 $k$ 个点，我们现在要找到一个点 $x_1$，使得 $x_1$ 到其它 $k$ 个点的距离和最短。这是一个经典问题，当 $x_1$ 取所有数的中位数时，总距离最小。
因此在求出环外各边权值的绝对值之和后，计算环上各边的权值，按上述步骤求处环上边的最小权值和即可。
## 3 基环树且环为奇环
对于奇环的情况，考虑断掉环上的一条边后，整个图变成了一棵树，我们仍然对这棵树黑白染色，则该断掉的边的两个端点同色。
因此，这一条边的作用即为，当该边的两个端点颜色**相同**时，将两个端点的颜色取反。
这样，我们可以不断生成 $2$ 个黑点或白点，这种情况下，黑点与白点的差值只会加 $2$ 或减 $2$，同时，我们的目标是让原图中所有点的颜色被取反。
所以，我们得到了这种情况下，无解的充要条件是：在断掉环上的一条边并对这棵树黑白染色后，黑白点个数奇偶性相同，当然，这与“$N$ 为偶数”这一条件是等价的。
由树的情况，我们可以证明，这一条边只能不断生成黑点或不断生成白点（具体的，考虑这种情况是答案的下界，可以先把答案加上生成次数，再在这个结点上叠若干个黑点或白点，发现叠黑点的情况可以使树中的两个结论都成立）。
因此令 $x$ 为黑点个数减白点个数，则整棵树的权值和为 $x$，先将答案加上 $\frac{|x|}{2}$，然后叠黑点或白点，即将两个点的权值减去 $\frac{x}{2}$（注意整棵基环树的权值和为 $0$ 时，我们才能恰好补齐黑点或白点并把边割掉转化为树，原因在于，注意到我们每次加黑点或者白点，不仅加上了两个被生成的点的权值，还减去了两个被替换的异色点的权值，而在原树中我们并没有减去这些被替换点的贡献，这与被生成的点的权值恰好相抵消），再跑树的做法即可。
（想不到更好的讲法，若有请告知 QwQ）
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 100005;
int n;
bool col[N];
vector<int> e[N];
ll ans = 0, val[N];
void Dfs(int u, int fa, bool pcol) {
col[u] = !pcol;
for(auto v : e[u]) {
if(v == fa) {
continue;
}
Dfs(v, u, col[u]);
}
}
ll Dfs2(int u, int fa) {
ll res = val[u];
for(auto v : e[u]) {
if(v == fa) {
continue;
}
res += Dfs2(v, u);
}
ans += abs(res);
return res;
}
vector<int> st;
bool vis[N], c[N], suc = false;
int cnt = 0;
vector<int> cir;
void Dfs3(int u, int fa) {
st.emplace_back(u);
vis[u] = true;
for(auto v : e[u]) {
if(v == fa) {
continue;
}
if(vis[v]) {
if(!suc) {
suc = true;
bool b = false;
for(auto x : st) {
if(x == v) {
b = true;
}
c[x] = b, cnt += b;
if(b) {
cir.emplace_back(x);
}
}
}
continue;
}
Dfs3(v, u);
}
st.pop_back();
}
void Dfs4(int u, bool pcol) {
col[u] = !pcol, vis[u] = true;
for(auto v : e[u]) {
if(vis[v]) {
continue;
}
Dfs4(v, col[u]);
}
}
ll Dfs5(int u, int fa) {
ll res = col[u] ? 1 : -1;
for(auto v : e[u]) {
if(v == fa || c[v]) {
continue;
}
res += Dfs5(v, u);
}
ans += abs(res);
return res;
}
int main() {
int i, m;
n = Read(), m = Read();
for(i = 1; i <= m; i++) {
int u = Read(), v = Read();
e[u].emplace_back(v), e[v].emplace_back(u);
}
if(m == n - 1) {
Dfs(1, 0, false);
int sum = 0, i;
for(i = 1; i <= n; i++) {
sum += col[i];
val[i] = col[i] ? 1 : -1;
}
if(sum * 2 != n) {
printf("-1");
return 0;
}
Dfs2(1, 0);
Write(ans);
return 0;
}
Dfs3(1, 0);
if(cnt & 1) {
int u, v;
for(i = 1; i <= n; i++) {
if(c[i]) {
u = i;
break;
}
}
for(auto x : e[u]) {
if(c[x]) {
v = x;
break;
}
}
for(i = 0; i < e[u].size(); i++) {
if(e[u][i] == v) {
break;
}
}
e[u].erase(e[u].begin() + i);
for(i = 0; i < e[v].size(); i++) {
if(e[v][i] == u) {
break;
}
}
e[v].erase(e[v].begin() + i);
Dfs(1, 0, false);
int sum = 0, i;
for(i = 1; i <= n; i++) {
sum += col[i];
val[i] = col[i] ? 1 : -1;
}
if(n & 1) {
printf("-1");
return 0;
}
ll x = n / 2 - sum;
val[u] += x, val[v] += x;
Dfs2(1, 0);
Write(ans + abs(x));
}
else {
memset(vis, 0, sizeof(vis));
Dfs4(1, false);
int sum = 0;
for(i = 1; i <= n; i++) {
sum += col[i];
val[i] = col[i] ? 1 : -1;
}
if(sum * 2 != n) {
printf("-1");
return 0;
}
memset(vis, 0, sizeof(vis));
vector<ll> vec;
for(auto v : cir) {
ll x = Dfs5(v, 0);
vec.emplace_back(x), ans -= abs(x);
}
for(i = 1; i < vec.size(); i++) { // \sum val_i = 0
vec[i] += vec[i - 1];
}
sort(vec.begin(), vec.end());
ll x = vec[vec.size() / 2];
for(auto v : vec) {
ans += abs(x - v);
}
Write(ans);
}
return 0;
}
```