给定一个 \(N\) 个点，\(M\) 条边的图，没有自环，没有重边。其中 \(N-1\le M\le N\)，每个点初始是白色。每次操作可以处理一条边，其两个点如果颜色相同则都变成相反的颜色（黑变白，白变黑）。询问能否将每个点都变为黑色。如果能，输出最少的操作数；如果不能，输出 \(-1\)。
\(N,M\le 10^5\)
先考虑树的情况。巧妙地，把树给黑白染色，那么把两个相同颜色的取反可以看作交换两个点的颜色，那么目标是把所有颜色翻转。
考虑什么情况下有解，当且仅当两种颜色数量相同。如果设黑色点权值为-1，白色点权值为 1，那么一条边交换的次数一定是左右黑色数量只差除以2，也就是子树权值绝对值除以2。
这里是容易算的，然后看一下奇环的基环树，黑白染色后一定有两个相邻点颜色相同，那么如果按照刚刚的方法分析，操作这条边相当于把相邻两个同颜色的点取反。这条边的操作次数是固定的，取决于两种颜色数量差。如果黑色比白色多 \(x\)，这条边会翻转 \(x/2\) 次。无解当且仅当 \(x\) 为奇数。那么提前翻转这么多次后，就和树的做法一样了。
然后看偶环基环树，假设某条边修改次数为 \(x\)，我们可以在树上得到每条边最少被反转的次数为 \(|c_i-x|\)，现在要使绝对值之和最小，\(x\) 去 \(c_i\) 的中位数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,m,fa[N],f,p,q,vs[N],k,w[N],a[N],h[N],d[N];
vector<int>g[N];
LL ans;
void dfs(int x,int y)
{
d[x]=d[y]+1,a[x]=w[x],fa[x]=y;
for(int v:g[x])
{
if(v==y)
continue;
if(!w[v])
w[v]=-w[x],dfs(v,x),a[x]+=a[v];
else
p=x,q=v,f=w[x]==w[v];
}
}
void sou(int x,int y)
{
a[x]=w[x];
for(int v:g[x])
if(v^y&&(x^p||v^q)&&(x^q||v^p))
sou(v,x),a[x]+=a[v];
}
int main()
{
scanf("%d%d",&n,&m);
if(n&1)
{
puts("-1");
return 0;
}
for(int i=1,u,v;i<=m;i++)
scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
dfs(w[1]=1,0);
if(m==n-1)
{
if(a[1])
return puts("-1"),0;
else
{
for(int i=1;i<=n;i++)
ans+=abs(a[i]);
}
}
else if(f)
{
ans+=abs(a[1]>>1);
w[p]-=a[1]>>1,w[q]-=a[1]>>1;
sou(1,0);
for(int i=1;i<=n;i++)
ans+=abs(a[i]);
}
else
{
if(a[1])
return puts("-1"),0;
int u=p,v=q;
while(u^v)
{
//printf("%d %d\n",u,v);
if(d[u]>d[v])
h[++k]=a[u],u=fa[u];
else
h[++k]=-a[v],v=fa[v];
}
sort(h+1,h+k+1);
int x=h[k+1>>1];
u=p,v=q;
while(u^v)
{
if(d[u]>d[v])
a[u]-=x,u=fa[u];
else
a[v]+=x,v=fa[v];
}
for(int i=1;i<=n;i++)
ans+=abs(a[i]);
ans+=abs(x);
}
printf("%lld",ans);
}