Solution
題意：給定一個(gè)無(wú)向圖，有一些邊已經(jīng)染色，求讓你染色剩下的邊使得每個(gè)環(huán)的異或和都為0的方案數(shù)。

好難想!好難想!好難想!重要的事情要說(shuō)三遍!

1.思維點(diǎn)：題解很巧妙，把對(duì)邊染色轉(zhuǎn)移到對(duì)點(diǎn)染色，取邊為兩個(gè)端點(diǎn)的xor，這樣的話每個(gè)環(huán)的異或和肯定為0，因?yàn)槊總€(gè)點(diǎn)都xor了兩次~

2.答案的貢獻(xiàn)：
考慮一個(gè)聯(lián)通塊里面沒(méi)有邊被染色，那么每個(gè)點(diǎn)都有染成 0/1 的選擇，設(shè)cnt為聯(lián)通塊中的點(diǎn)數(shù)目，那么可以考慮成 2^cnt， 但是想一下，因?yàn)槭撬氵叺娜旧桨付皇屈c(diǎn)的染色方案，如果對(duì)所有點(diǎn)取反，邊權(quán)不變，所以每個(gè)聯(lián)通塊對(duì)答案的貢獻(xiàn)為： 2^(cnt-1) 。

再考慮已經(jīng)有x條邊被染色的聯(lián)通塊，那么如果這些染色的邊已經(jīng)有一個(gè)點(diǎn)確定一個(gè)值，那么染色的邊剩下的點(diǎn)的值就都確定了，所以每個(gè)連通塊對(duì)答案的貢獻(xiàn)要除以： 2^x (x條邊有x+1個(gè)點(diǎn))

3.判斷合法性：類似于判斷二分圖染色一樣，遍歷已經(jīng)確定的邊和隨便染上1/0，根據(jù)邊權(quán)由點(diǎn)權(quán)異或得到判斷是否沖突。

參考題解，用三個(gè)dfs來(lái)解決問(wèn)題：
dfs1: 慢慢染色，看是否合法。
dfs2: 統(tǒng)計(jì)所有聯(lián)通塊的點(diǎn)數(shù)
dfs3: 統(tǒng)計(jì)有染色邊的聯(lián)通塊中的點(diǎn)數(shù)

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=1e5+5;

vector<pair<ll,ll> >g[manx];
ll col[manx],vis[manx];
ll cnt=0;

ll dfs1(ll u,ll co){
    col[u]=co;
    for(auto x: g[u]){
        ll v=x.fi,w=x.se;
        if(w==-1) continue;
        if(col[v]!=-1 && co^col[v]!=w) return 0;
        if(col[v]==-1 && !dfs1(v,co^w)) return 0;
    }
    return 1;
}

void dfs2(ll u){
    cnt++; vis[u]=1;
    for(auto x:g[u]){
        ll v=x.fi,w=x.se;
        if(vis[v]) continue;
        dfs2(v);
    }
}

void dfs3(ll u){
    cnt++; vis[u]=1;
    for(auto x:g[u]){
        ll v=x.fi,w=x.se;
        if(vis[v]||w==-1) continue;
        dfs3(v);
    }
}
int main(){
    ll n=read(),m=read();
    for(int i=1;i<=m;i++){
        ll u=read(),v=read(),w=read();
        g[u].pb(mp(v,w));  g[v].pb(mp(u,w));
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++){
        if(col[i]==-1){
            if(!dfs1(i,1)){
                cout<<0<<endl;
                return 0;
            }
        }
    }
    ll k=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt=0;
            dfs2(i);
            k+= cnt-1;
        }
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt=0;
            dfs3(i);
            k-= cnt-1;
        }
    }
    ll ans=1;
    for(int i=1;i<=k;i++){
        ans=ans*2;
        ans%=mo;
    }
    printf("%lld\n",ans);
    return 0;
}