5895. 【NOIP2018模拟10.5】旅游

题目大意：

思路：

这题目比较特殊点在于他的边权是2^i，比赛的时候傻，没有想到有什么用，后来看到题解，如果构出一颗最小生成树，那么最短路一定在最小生成树上面，这样子就变成了一棵树上在原图中的奇点要配对，因为树上的一些奇怪性质，我们可以之间贪心得出答案，最后答案就是所有边权加上最小生成树上面贪心的结果。

程序：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mo 998244353
#define N 500005
#define LL long long
using namespace std;

LL du[N],last[N],g[N],fa[N],n,m,v,u,o,ans,cnt,s;
struct tree{LL to,next,w;}e[N*2];

void add(LL x,LL y,LL w){
	e[++cnt].to=y; e[cnt].next=last[x]; e[cnt].w=w; last[x]=cnt;
	e[++cnt].to=x; e[cnt].next=last[y]; e[cnt].w=w; last[y]=cnt;
}

void dfs(int x,int fa){
	if (du[x]%2==1) g[x]=1;
	for (int i=last[x];i;i=e[i].next)
	if (e[i].to!=fa){
		dfs(e[i].to,x);
		if (g[e[i].to]) ans=(ans+e[i].w)%mo;
		g[x]=g[x]^g[e[i].to];
	}
}

LL father(LL x){
	if (fa[x]!=x) o=father(fa[x]);
			else o=x;
	fa[x]=o;
	return o;
}

int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for (LL i=1;i<=n;i++) fa[i]=i;
	s=1;
	for (LL i=1;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		s=(s*2)%mo;
		ans=(ans+s)%mo;
		du[u]++,du[v]++;
		LL x=father(u),y=father(v);
		if (x!=y){
			add(u,v,s);
			fa[x]=y;
		}
	}
	dfs(1,0);
	printf("%lld",ans%mo);
}