题目大意

给定一张 n 个点 m 条边的无向连通图, 初始时每个点均为白色。每次你可以选择一条两个端点颜色相同的边, 并将它们一起变色 (白变黑, 黑变白)。你需要求出将每个点均变为黑色的最少步数。

数据范围

$$1 \leq n \leq 10^5, n-1 \leq m \leq n$$

题目分析

对于树

由于树是一种二分图，所以我们可以将所有点二分染色，相当于将一些点反色，问题转化为使整棵树所有节点反色的最少步数。

那么我们可以在所有的黑点上放上一枚硬币，然后问题转化为黑点将硬币沿边转移到白点上，使得所有黑点上没有硬币，所有白点上都有一枚的方案数。

按照一般贪心思想，将黑点的点权设为 1，白点点权设为-1. 然后求子树点权和 $f(x)$。假如子树的点权和是正，说明要有一些硬币从子树里转移出去。若为负，则说明要有一些转移进来。转移出去和进来花费都是 1，所以答案就是 $\sum abs(f(x))$

而无解的情况就是 $f(root)!=0$的情况啦。

对于奇环

现在树上多了条边，形成了一个奇环。那么该边两端的点应该是同色的，那么我们可以选择该边若干次，将该边两端的点上的硬币（带权，硬币数量可以是负数，可以理解为对硬币的需求量）同时消失。

那么我们知道，对树跑一遍上面讲的 dp 后，若 $f(x)$不为 0，说明有多余的硬币不知道往哪里放，那么就应该通过这两点将硬币消灭。所以对这两个点的点权同时减去 $\frac{f(x)}{2}$即可。当然，如果 $f(x)$不能被 2 整除，显然是无解的。

对于偶环

现在树上多了条边，形成了一个偶环。那么该边两端的点应该是异色的，那么我们只是多了一条可以转移硬币的边而已。我们假设通过这条边转移了 $x$枚硬币（同样可以是负数）。那么该边一端的点 a 的硬币数应该减 x，另一边的点 b 应该加上 x。

a 所在的子树硬币数应该减去 x，b 所在的子树硬币数应该加上 x。那么我们设第二个权值 $g(a)=-1$，$g(b)=1$，其他 g 值为子树里 g 值和。这样的花，答案就应该是：

$$abs(x)+\sum abs(f_i+g_ix)$$

不知道米娜桑有没有做过这样一道题洛谷 P3819 松江 1843 路，这道题里就提到了对于这种式子的经典贪心方法。首先对于 $g_i=0$，直接计算 $f_i$的贡献。否则由于 $g_i$只有两个取值，-1 和 1，所以可以看作数轴上有若干个点，每个点的坐标是 $f_ig_i$，找一个点，使得该点到其他所有点的距离和最优。由那道题的贪心思想，可以知道 x 取所有点的中位数最优。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005;
int n,m,T,tot,uu,vv,ww,ans,js;
int h[N],ne[N<<1],to[N<<1];
int a[N],b[N],f[N],g[N],kl[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x,int las) {
    for(int i=h[x];i;i=ne[i]) {
        if(to[i]==las) continue;
        if(!a[to[i]]) a[to[i]]=-a[x],dfs(to[i],x);
        else uu=x,vv=to[i],ww=(a[to[i]]==a[x]);
    }
}
void dp(int x,int las) {
    f[x]=a[x],g[x]=b[x];
    for(int i=h[x];i;i=ne[i]) {
        if(to[i]==las||(x==uu&&to[i]==vv)||(x==vv&&to[i]==uu)) continue;
        dp(to[i],x),f[x]+=f[to[i]],g[x]+=g[to[i]];
    }
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int x,y;
    T=read();
    while(T--) {
        n=read(),m=read();
        tot=ans=0;for(int i=1;i<=n;++i) h[i]=0;
        for(int i=1;i<=m;++i) x=read(),y=read(),add(x,y),add(y,x);
        if(n&1) {puts("-1");continue;}
        for(int i=1;i<=n;++i) a[i]=b[i]=0;
        a[1]=1,dfs(1,0);
        if(m==n-1) {//对于树
            dp(1,0);
            if(f[1]) {puts("-1");continue;}//无解
            for(int i=1;i<=n;++i) ans+=abs(f[i]);
            printf("%d\n",ans);continue;
        }
        if(ww) {//对于奇环
            dp(1,0);
            if(f[1]%2) {puts("-1");continue;}
            ans+=abs(f[1]/2),a[uu]-=f[1]/2,a[vv]-=f[1]/2,dp(1,0);
            for(int i=1;i<=n;++i) ans+=abs(f[i]);
            printf("%d\n",ans);
        }
        else {//对于偶环
            b[uu]=1,b[vv]=-1,dp(1,0),js=0;
            if(f[1]) {puts("-1");continue;}
            for(int i=1;i<=n;++i)
                if(!g[i]) ans+=abs(f[i]);
                else kl[++js]=g[i]*f[i];
            kl[++js]=0,sort(kl+1,kl+1+js);//kl[++js]=0: 由于答案里还有一个 abs(x), 所以 0 也应该加进去
            int zws=kl[(js+1)/2];
            for(int i=1;i<=js;++i) ans+=abs(kl[i]-zws);
            printf("%d\n",ans);
        }
    }
    return 0;
}