边的染色

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。
现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：
对于G中任意一个环，里面所有边的边权的异或值为0。
环的定义如下：
对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<k满足ai与ai+1之间有边，且a1=ak成立，则这k个点构成一个环。

思路：

参考了该题解：https://blog.csdn.net/jaihk662/article/details/80955631
如该题解所说，首先换边权为点权，既边权为它连接的二个点权的异或值，这样对于一个环而言，所有边的异或值为0（相当于每个点权异或二次），在一个联通块中如果全为不确定的边，则该连通块的n个点一共有2的(n）次方的情况，但当一种点权值全取反时边权值全不变，所以情况为2的（n-1）次方，当有一条边确认时，边的一个端点确认时另一个端点也会确认，则会产生一个已确定的点，方案数则要除以二，所以一个有n个点(k个点为已确定的点)的连通块的方案数为2的(n-1)次方除以2的k次方，既2的（未确定的点个数-1）次方。用并查集统计联通块的情况。

注意：当一个环全为确定的边时，如果环边的异或值为1则方案数为0.

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 998244353

int n, m, pre[100005], ran[100005], flag=1, f[100005], ma[100005], fa[100005];
//ma数组统计连通块点的个数， fa统计联通块已确定的点的个数。
struct w
{
    int to, w;
}w;

vector<struct w> g[100005];

void inti()
{
    for(int i=0; i<=n; i++)
    {
        pre[i]=i;
        ran[i]=0;
    }
}

int find(int x)
{
    if(x==pre[x])
    {
        return x;
    }
    pre[x]=find(pre[x]);
    return pre[x];
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        if(ran[x]<ran[y])
        {
            pre[x]=y;
        }
        else
        {
            pre[y]=x;
            if(ran[x]==ran[y])
            {
                ran[x]++;
            }
        }
    }
}

bool same(int x,int y)
{
    return find(x)==find(y);
}

int dfs(int v,int pa,int k, int wa)
{
    if(pa==-1)
    {
        f[v]=1;
    }
    else
    {
        f[v]=f[pa]^wa;
        k++;
    }
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i].w!=-1)
        {
            if(pa!=g[v][i].to&&f[g[v][i].to]==-1)
            {
                k=k+dfs(g[v][i].to,v,0,g[v][i].w);
            }
            else if(f[g[v][i].to]!=-1)
            {
                if(f[g[v][i].to]^f[v]!=g[v][i].w)
                {
                    flag=0;
                }
            }
        }
    }
    return k;
}

ll fun(ll d,ll k)
{
    ll s=1;
    while(k)
    {
        if(k&1)
        {
            s=s*d%inf;
        }
        d=d*d%inf;
        k=k/2;
    }
    return s;
}

int main()
{
    scanf("%d %d",&n,&m);
    inti();
    memset(f,-1,sizeof(f));
    for(int i=0; i<m; i++)
    {
        int u, v, t;
        scanf("%d %d %d",&u,&v,&t);
        w.to=v;
        w.w=t;
        g[u].push_back(w);
        w.to=u;
        g[v].push_back(w);
        unite(u,v);
    }
    for(int i=1; i<=n; i++)
    {
        ma[find(i)]++;
    }
    ll ans=1;
    for(int i=1; i<=n; i++)
    {
        if(f[i]==-1&&ma[find(i)]!=1)
        {
            int pan=dfs(i,-1,0,-1);
            fa[find(i)]+=pan;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(ma[find(i)]>1)
        {
            ans=ans*fun(2,ma[find(i)]-1-fa[find(i)])%inf;
            ma[find(i)]=1;//防止同一个连通块重复计算
        }
    }
    if(flag==0)
    {
        ans=0;
    }
    printf("%lld\n",ans);
    return 0;
}