传送门
先考虑树，树是一个二分图。
看到是二分图并且每次是对两边的同色的点反色可以想到转化：让奇数层的点为黑，偶数为白，变成每次可以交换两个点的颜色。
把黑看成 \(-1\)，白看成 \(1\)，那么求一个子树和，考虑每一条边的贡献可以得到 \(ans=\sum_{i=1}^{n} |sum_i|\)
如果根的 \(sum\) 不为 \(0\)，那么肯定是无解的。
对于基环树，先考虑奇环。
断开奇环的一条边 \((u,v)\)，变成树，\(u,v\) 肯定是同一边的点。
操作一次 \((u,v)\) 相当于可以两边可以同时新增加白点/黑点，也就是可以把根的 \(sum\) 用这两个点来变成 \(0\)，(\(sum\) 必须为偶数)平均分配之后用树的做法即可。
考虑偶环。
断开偶环的一条边 \((u,v)\)，变成树，\(u,v\) 肯定不是同一边的点。
操作一次 \((u,v)\) 相当于是让左右的点走了一次捷径。
设用的次数为 \(x\)。
如果一个点同时包含或不包含 \(u,v\) 两个点，那么 \(sum\) 一定不变。
否则加上或者减去 \(x\)。
相当是是要求 \(|x|+\sum |sum_i-x| + \sum |sum_i+x|\)
经典问题，排序之后取中位数即可。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e5 + 5);
struct Edge { int to, next; };
int n, m, first[maxn], cnt, sum[maxn], fa[maxn], dsu[maxn], deep[maxn], a, b, ans, val[maxn];
Edge edge[maxn << 1];
inline int Find(int x) { return (dsu[x] ^ x) ? dsu[x] = Find(dsu[x]) : x; }
inline void Add(int u, int v) {
edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
edge[cnt] = (Edge){u, first[v]}, first[v] = cnt++;
}
void Dfs(int u, int ff, int d) {
int e, v;
sum[u] = d;
for (e = first[u]; ~e; e = edge[e].next)
if ((v = edge[e].to) ^ ff) {
deep[v] = deep[u] + 1;
fa[v] = u, Dfs(v, u, -d);
sum[u] += sum[v];
}
}
int main() {
int i, u, v, len = 1;
memset(first, -1, sizeof(first));
scanf("%d%d", &n, &m);
if (n & 1) return puts("-1"), 0;
for (i = 1; i <= n; ++i) dsu[i] = i;
for (i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
if (Find(u) ^ Find(v)) Add(u, v), dsu[Find(u)] = Find(v);
else a = u, b = v;
}
if (!a) {
Dfs(1, 0, 1);
if (sum[1]) return puts("-1"), 0;
}
else {
Dfs(a, 0, 1);
if (deep[b] & 1) {
if (sum[a]) return puts("-1"), 0;
for (i = b; i ^ a; i = fa[i]) val[++len] = sum[i], sum[i] = 0;
sort(val + 1, val + len + 1), v = val[(len + 1) >> 1];
for (i = 1; i <= len; ++i) ans += abs(val[i] - v);
}
else {
if (sum[a] & 1) return puts("-1"), 0;
v = sum[a] >> 1, ans = abs(v), sum[a] = 0;
for (i = b; i ^ a; i = fa[i]) sum[i] -= v;
}
}
for (i = 1; i <= n; ++i) ans += abs(sum[i]);
printf("%d\n", ans);
return 0;
}