Description
现在给你一张\(N\)个点\(M\)条边的连通图，我们保证\(N−1\leqslant M \leqslant N\)，且无重边和自环。
每一个点都有一种颜色，非黑即白。初始时，所有点都是白色的。
“全”想通过执行若干次某种操作的方式，来将所有的点变成黑色。操作方式如下：
选择一对颜色相同的相邻的节点（存在边直接连接彼此），将它们的颜色反转。即若原来都是白色，则都变成黑色，反之亦然。
现在“全”想知道，他能否通过执行这种操作以达到目的。如果可以，他还希望步数尽可能的少。
Hint
Solution
发现\(N−1\leqslant M \leqslant N\)所以原图要么是一棵树要么是一颗环套树（只有一个环）。
树的做法
我们考虑转换模型，注意到树是一个二分图，所以我们将树分成奇数层和偶数层，奇数层有一个空位，而偶数层有一个棋子，那么将边的颜色反转的过程可以看成将棋子进行移动。那么可以发现仅当空位数=硬币数时问题有解。
然后，考虑最小步数，我们记硬币为-1，空位为1，\(S_i\)表示子树和，那么\(K=\sum_{i=1}^{n}{Si}\)，考虑意义\(S_i\)表示的是\(i\to u\)这条边的贡献，发现K为原问题答案的下界。
又因为对于\(\forall u\in [1,n]\)我们可以将他的儿子钦定为“+儿子”和“-儿子”，每次把“+儿子”的硬币匹配“-儿子”的空位，即可，问题解决。
奇环
断开奇环上的一条边\((u,v)\)得到一棵树，由于是奇环，所以u，v的奇偶性一致。所以\((u,v)\)这条边对应的操作就是，将两个同层的点，同时加上或者减去一定数量的硬币。那么我们就先计算出断开后的树，缺了多少个空位或者硬币，如果是奇数则无解，否则就平摊给u，v，然后类似树的做法，统计答案即可。
偶环
断开偶环上的一条边\((u,v)\)得到一棵树，由于是偶环，所以u，v的奇偶性不一致。所以，\((u,v)\)这条边对应的操作是，从u将x个硬币移到v上。那么我们记u的系数为1，v的系数为-1，并将子树分类：
1、系数为1，子树中仅包含u
2、系数为-1，子树中仅包含v
3、系数为0，子树中不包含u，v或者同时包含u，v
那么，答案就是\(ans=\sum_{i=1}^{n}{|k_ix+S_i|}+|x|\)
这就变成了一个经典问题，取中位数即可。
Code
/**************************************************************
Problem: 3175
User: ez_hjw
Language: C++
Result: Accepted
Time:61 ms
Memory:10168 kb
****************************************************************/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100000 + 10;
inline int rd() {
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
do{
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return x;
}
int n, m, cnt, h[maxn], sum = 0, flag, kx[maxn], val[maxn];
struct enode{
int v, n;
enode() {}
enode(int _v, int _n):v(_v), n(_n) {}
}e[maxn << 1];
inline void addedge(int u, int v) { cnt ++; e[cnt] = enode(v,h[u]); h[u] = cnt; }
int dep[maxn], vis[maxn], Sx, Tx, st[maxn];
void dfs(int u, int fa) {
dep[u] = dep[fa] ^ 1;
vis[u] = 1;
for(int i = h[u];~ i;i = e[i].n) {
int v = e[i].v;
if(v == fa) continue;
if(vis[v]) Sx = u, Tx = v, flag = (dep[u] == dep[v]);
else dfs(v,u);
}
}
void solve(int u, int fa) {
for(int i = h[u];~ i;i = e[i].n) {
int v = e[i].v;
if(v == fa) continue;
if((u == Sx && v == Tx) || (u == Tx && v == Sx)) continue;
solve(v,u);
val[u] += val[v];
kx[u] += kx[v];
}
}
int main() {
n = rd(); m = rd();
cnt = 0;
memset(h,-1,sizeof(h));
for(int i = 1;i <= m;i ++) {
int u, v;
u = rd(); v = rd();
addedge(u,v);
addedge(v,u);
}
flag = 0;
dep[0] = 0;
dfs(1,0);
int ans = 0;
for(int i = 1;i <= n;i ++) {
if(dep[i]) val[i] = 1;
else val[i] = -1;
sum += val[i];
}
if(m == n - 1) {
if(sum) {
puts("-1");
return 0;
}
}
else {
if(flag) {
if(sum & 1) {
puts("-1");
return 0;
}
val[Sx] -= sum / 2;
val[Tx] -= sum / 2;
ans += abs(sum) / 2;
}
else {
if(sum) {
puts("-1");
return 0;
}
kx[Sx] = 1;
kx[Tx] = -1;
}
}
solve(1,0);
int top;
st[top = 1] = 0;
for(int i = 1;i <= n;i ++) {
if(!kx[i]) ans += abs(val[i]);
else st[++ top] = - val[i];
}
sort(st + 1,st + top + 1);
int k = st[(top + 1) >> 1];
for(int i = 1;i <= top;i ++) {
ans += abs(st[i] - k);
}
printf("%d\n", ans);
return 0;
}
居然上榜了