【题解】
我们可以发现不在最小生成树上的边一定不能多次经过，因为一条不在最小生成树上的边(u,v)的边权比最小生成树上(u,v)之间的路径更长，选择不在最小生成树上的边一定不划算。
我们还需要确定最小生成树上哪些边需要经过两次。我们发现如果某个点当前的度为奇数，这个点到它的父亲的边要经过两次，所以我们在它和它父亲之间多连上一条边(即把他们的度都加1）.
这样一次dfs我们就可以从下往上确定出需要经过两次的边。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define N 500010 6 #define rg register 7 using namespace std; 8 const int Mod=998244353; 9 int n,m,tot,cnt,last[N],in[N],fa[N]; 10 LL ans,Pow[N]; 11 struct edge{int to,pre,dis;}e[N<<1]; 12 struct rec{int u,v;}r[N]; 13 inline int read(){ 14 int k=0,f=1; char c=getchar(); 15 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17 return k*f; 18 } 19 void dfs(int x,int f,int eg){ 20 for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=f) dfs(to,x,i); 21 if((in[x]&1)&&x!=1) ans=(ans+Pow[e[eg].dis])%Mod,in[f]++; 22 } 23 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} 24 int main(){ 25 n=read(); m=read(); Pow[0]=1; 26 for(rg int i=1;i<=m;i++){ 27 Pow[i]=(Pow[i-1]<<1)%Mod; ans=(ans+Pow[i])%Mod; 28 in[r[i].u=read()]++; in[r[i].v=read()]++; 29 } 30 for(rg int i=1;i<=n;i++) fa[i]=i; 31 for(rg int i=1;i<=m;i++){ 32 int u=r[i].u,v=r[i].v; 33 if(find(u)!=find(v)){ 34 e[++tot]=(edge){u,last[v],i}; last[v]=tot; 35 e[++tot]=(edge){v,last[u],i}; last[u]=tot; 36 fa[find(u)]=find(v); 37 cnt++; if(cnt==n-1) break; 38 } 39 } 40 dfs(1,0,0); 41 printf("%lld ",ans); 42 return 0; 43 }