题目
题目大意
给你一个无向图，让你从起点出发，经过所以边至少一次的最小时间。
思考过程
2i2^i2i这个东西值得深思。
可以发现两点之间的最短路径的长度大于最短路径上的最长边，小于它的两倍。
因为最短路径中一个边不可能经过两次，对于最长边mxmxmx，任意∑i<mx2i≤2mx\sum_{i<mx}{2^i} \leq 2^{mx}∑i<mx2i≤2mx
这是很显然的。
很容易想出这题或许和最小生成树有关系。
如果要求两点间的最短路，就要使路径上的最长边最小。
因为最小生成树后，对于两个点uuu和vvv，它们的最短路径路径一定在树上。
如果有一条非树边(u,v)(u,v)(u,v)，(u,v)(u,v)(u,v)的长度必定小于它们在树上的路径长度。
所以每一条非树边只会经过一次。
然后呢，然后呢，我就想不出什么性质了……
正解
要用到一个叫欧拉回路的东西。
无向图中，如果每个点的度数为偶数，那么就是欧拉回路（可以理解成能够一笔画的图），否则不是。
在这题中，每个点不一定都是奇数度数。
所以我们要将那些奇数度数的点两两配对。
配对后给它们之间加一条边，这条边的长度即是最小生成树上两点之间的路径长度。
然后整个图就变成了一个欧拉回路了……
那么如何两两配对？
其实我们并不需要真正地两两配对。
对于树上的一个点xxx，如果它的子树的奇数度点的个数为奇数时，说明在那些点中肯定有一个点，必定是和子树外面的点配对，所以就必须经过xxx和它的父亲之间的那条边。
所以直接记录下贡献就好了。
还有，每条边最多经过两次……
怎么证明呢？感性理解吧，我不会。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 500000
#define MAXM 500000
#define mod 998244353
int n,m;
int pow2[MAXM+1];
struct edge{
int u,v;
} ed[MAXM+1];
int fa[MAXN+1];
int getfa(int x){
if (fa[x]==x)
return x;
return fa[x]=getfa(fa[x]);
}
struct EDGE{
int to,num;
EDGE *las;
} e[MAXM*2+1];
int ne;
EDGE *lst[MAXN+1];
inline void link(int u,int v,int num){
++ne;
e[ne]={v,num,lst[u]};
lst[u]=e+ne;
}
int d[MAXN+1];
int sum[MAXN+1];
void dfs(int,int);
int ans=0;
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%d%d",&n,&m);
pow2[0]=1;
for (int i=1;i<=m;++i){
pow2[i]=(pow2[i-1]<<1)%mod;
ans=(ans+pow2[i])%mod;//每个点至少经过一次
}
for (int i=1;i<=m;++i){
scanf("%d%d",&ed[i].u,&ed[i].v);
d[ed[i].u]++;
d[ed[i].v]++;
}
//最小生成树
for (int i=1;i<=n;++i)
fa[i]=i;
for (int i=1;i<=m;++i){
int x=getfa(ed[i].u),y=getfa(ed[i].v);
if (x!=y){
fa[x]=y;
link(ed[i].u,ed[i].v,i),link(ed[i].v,ed[i].u,i);
}
}
dfs(1,0);
printf("%d\n",ans);
return 0;
}
void dfs(int x,int fa){
sum[x]=d[x];
for (EDGE *ei=lst[x];ei;ei=ei->las)
if (ei->to!=fa){
dfs(ei->to,x);
sum[x]^=sum[ei->to];//其实真正有价值的是二进制的第0位，直接异或起来只是方便了
if (sum[ei->to]&1)
ans=(ans+pow2[ei->num])%mod;//统计答案
}
}
总结
欧拉回路……