纪念一下第一次补完 div1 的所有题
这个 1E 相较于其他的 1E 并不算太难。本题解部分参考官方题解。
先观察到一条边是好的当且仅当它的值和一个端点的值相同。
原因很简单，要求两端点值不同，若边权跟点权也不同，那么三个值分别只能为 \(1,2,3\)，又因为 \(1 \oplus 2 \oplus 3=0\)，不符合原条件。
那么我们假设两端点分别为 \(u,v\)，如果边权与 \(u\) 的值相同就让 \(v\) 连向 \(u\)，反之 \(u\) 连向 \(v\)，那我们也就相当于要让边定向。
再观察到一个点是好的当且仅当它的出边度数为奇数。
还是反证法，如果一个点的出边度数为偶数，不妨设当前点的点权为 \(2\)（为其他值的时候同理），那么所有出边的异或和只能是 \(2\) 或者 \(0\)，又因为所有入边的值为当前点的点权 \(2\)，所以最终的异或和只能为 \(0\) 或者 \(2\)，不符合条件。
那我们就成功的将题目转换为两部分：给所有点赋点权以及给所有边定向。分开计算最后相乘即可。
第一部分：
注意到原图是一个仙人掌，我们把原图的所有割边去掉就会成为若干个环。
注意到一条割边的两边贡献独立，只会在此处进行合并，具体地，如果两边的贡献分别为 \(x,y\)，那么最后的答案为 \(\dfrac{2}{3}xy\) ，原因是一条边的两个端点值不能相同。
现在就将仙人掌拆成了若干个环，也就转换为长为 \(n\) 的环可以染 \(k\) 种颜色，相邻两点颜色不同的方案数。
这是一个 经典问题，直接使用结论，设长为 \(n\) 的环的答案为 \(s_n\) ，那么有 \(s_n=(k-1)^n+(-1)^n(k-1)\) ，在本题中，\(k=3\)，当然你也可以打表/归纳法来找到通项公式。
注意：一个点也应该被视为一个环，但是通项公式只适用于 \(n>2\) ，需特殊处理一下。
那么这部分的答案为 \((\dfrac{2}{3})^p \prod s_{len}\)，\(p\) 为割边的总数量，\(len\) 为每个环的环长。
第二部分：
还是注意到原图是仙人掌，由若干个环（环长大于 \(2\) ）和若干个单点构成。
环的贡献显然为 \(2\)，每个点的出边可以都连向顺时针/逆时针的下一个点，那我们就可以把一个环看成一个点，将原图缩成一棵树。
注意到叶子节点，如果当前点有出边数量是奇数（如果是一个环缩成一个点的话当前点会有出边），那么叶子只能接受入边，否则只能接受出边。
那我们把叶子删掉，直到把整个树删完即可，树的定向方案是唯一的。
注意：有可能有无解情况，比如说删到最后删到只剩两个点，每个点都只能接受出边/入边此时就会无解。
但是直接模拟删叶子判无解会比较麻烦，巧妙地做法是从奇偶分析，\(n\) 个点都只有奇数条出边，每条边都会被计算一次，那个总条数也就是 \(m\)，那么有解当前仅当 \(n,m\) 奇偶性相同。
这部分的答案为 \(2^{cnt}\)，\(cnt\) 为环长大于 \(2\) 的环长总个数。
实现精细能也许能做到线性，但是笔者比较懒，什么都是暴力做的，复杂度为 \(O(n \log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+3,H=998244353;
ll n,m,px[N],py[N],pz[N],tim,dfn[N],low[N],f[N],sz[N];
bool v[N];
struct Nod{ll y,id;};
vector<Nod>ve[N];
ll Ksm(ll x,ll y)
{
ll s=1;
for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
return s;
}
void Dfs(int x,int z)
{
dfn[x]=low[x]=++tim;
for(Nod t:ve[x])if(t.id!=z)
{
if(dfn[t.y]){low[x]=min(low[x],dfn[t.y]);continue;}
Dfs(t.y,t.id);low[x]=min(low[x],low[t.y]);
if(low[t.y]>dfn[x])v[t.id]=1;
}
}
ll F(ll x){return f[x]==x?x:f[x]=F(f[x]);}
ll Ans(ll x){return x==1?3:(Ksm(2,x)+(x%2==1?-1:1)*2+H)%H;}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>px[i]>>py[i]>>pz[i],ve[px[i]].push_back({py[i],i}),ve[py[i]].push_back({px[i],i});
if(n%2!=m%2){cout<<0;return 0;}
Dfs(1,0);ll sa=0,sb=1,sc=1;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
if(v[i])sa+=pz[i]+1,sb=sb*Ksm(3,pz[i])%H;
else if(F(px[i])!=F(py[i]))f[F(px[i])]=F(py[i]);
}
for(int i=1;i<=n;i++)sz[F(i)]++;
for(int i=1;i<=m;i++)if(!v[i])sz[F(px[i])]+=pz[i];
for(int i=1;i<=n;i++)if(sz[i]>1)sb=sb*2%H;
for(int i=1;i<=n;i++)if(sz[i])sc=sc*Ans(sz[i])%H;
sa=Ksm(2,sa)*Ksm(Ksm(3,H-2),sa)%H;
cout<<sa*sb%H*sc%H;
}