题目大意

题目链接
给一个无向图 边有黑白两种颜色。你每次可以指定一个回路上的所有的边颜色都反色。问至少多少次操作可以都变成白色。支持边颜色的修改。
$n \leq 10^6$

题解

这种题目就比较神仙，代码好写 但是思维难度不低（至少我这种菜鸡想不出来）
我们首先考虑如果有了一个方案 它有哪些性质。我们把所有的回路上每一次经过的边都连上去建一个新图。发现这个新图有如下性质：

1. 白边都经过偶数次
2. 黑边都经过奇数次
3. 所有的点都是偶数（因为回路拼起来）

所以我们可以得到有解的必要条件是每个点连的黑边个数为偶数个（减去所有白边）。如果每个点都满足这个性质很容易构造出一个关于黑边（们）的欧拉回路，所以还是一个充分条件。
我们考虑上述证明过程：对黑边求欧拉回路。那么我们发现如果没有白边 答案就只能是黑边的连通块数量。加入所有的白边 在一个连通块里的黑边就可以一次到达了。所以答案就是包含黑边的连通块个数。
Code：

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int n,m;
struct Edge{
    int u,v,c,id;
}e[MAXN];
int f[MAXN];
inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    f[x] = y;
}
int cnt[MAXN],du[MAXN];
int ct2[2],ans;
int main(){
    scanf("%d%d",&n,&m);FOR(i,1,n) f[i] = i;ct2[0] = n;
    FOR(i,1,m){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
        int u = e[i].u,v = e[i].v;
        merge(u,v);
        if(e[i].c == 1){
            ct2[du[u]&1]--;du[u]++;ct2[du[u]&1]++;
            ct2[du[v]&1]--;du[v]++;ct2[du[v]&1]++;
        }
    }
    FOR(i,1,m) e[i].id = find(e[i].u);
    FOR(i,1,m){
        if(e[i].c == 1){
            if(!cnt[e[i].id]) ans++;
            cnt[e[i].id]++;
        }
    }
    int q;scanf("%d",&q);
    FOR(i,1,q){
        int opt;scanf("%d",&opt);
        if(opt == 1){
            int x;scanf("%d",&x);++x;int u = e[x].u,v = e[x].v;
            if(e[x].c == 0){
                ct2[du[u]&1]--;du[u]++;ct2[du[u]&1]++;
                ct2[du[v]&1]--;du[v]++;ct2[du[v]&1]++;
                if(!cnt[e[x].id]) ans++;cnt[e[x].id]++;
            }
            else{
                ct2[du[u]&1]--;du[u]--;ct2[du[u]&1]++;
                ct2[du[v]&1]--;du[v]--;ct2[du[v]&1]++;
                if(cnt[e[x].id] == 1) ans--;cnt[e[x].id]--;
            }
            e[x].c ^= 1;
        }
        if(opt == 2){
            printf("%d\n",ct2[1]?-1:ans);
        }
    }
    return 0;
}