JZOJ5895. 【NOIP2018模拟10.5】旅游

题解

很显然，一条边至少走一次，最多走两次，
先建一棵最小生成树，
对于一条不在树上面的边，就将与它在最小生成树上构成的边的权值全部加一。
最后权值为偶数的边边权算两次，其余的都算一次。
如果被其他非最小生成树上面的经过偶数次，也就是要原路返回。

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#define N 500003
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
	n=0;
	ch=G();
	while((ch<'0' || ch>'9') && ch!='-')ch=G();
	int w=1;
	if(ch=='-')w=-1,ch=G();
	while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
	n*=w;
}

const int mo=998244353;
int f[19][N],nxt[N*2],lst[N],to[N*2],num[N*2],tot;
int n,m,x,y,xx,yy,z[N],fa[N],v[N],id[N],ans;
int l[N],r[N],w,q[N],head,tail,dep[N];

void ins(int x,int y,int z)
{
	nxt[++tot]=lst[x];
	to[tot]=y;
	num[tot]=z;
	lst[x]=tot;
}

void bfs()
{
	int x;
	for(head=0,q[tail=1]=1;head<tail;)
	{
		x=q[++head];dep[x]=dep[f[0][x]]+1;
		for(int i=lst[x];i;i=nxt[i])
			if(to[i]!=f[0][x])f[0][q[++tail]=to[i]]=x,id[to[i]]=num[i];
	}
}

int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int j=18;j+1;j--)
		if(dep[f[j][x]]>=dep[y])x=f[j][x];
	if(x==y)return x;
	for(int j=18;j+1;j--)
		if(f[j][x]!=f[j][y])x=f[j][x],y=f[j][y];
	return f[0][x];
}

int get(int x){return fa[x]=(fa[x]==x?x:get(fa[x]));}

int main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	
	read(n);read(m);tot=z[0]=1;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		read(x),read(y);
		xx=get(x);yy=get(y);
		if(xx!=yy)ins(x,y,i),ins(y,x,i),fa[xx]=yy;
		else w++,l[w]=x,r[w]=y;
		z[i]=z[i-1]*2%mo;
		ans=(ans+z[i])%mo;
	}
	
	bfs();
	for(int j=1;j<19;j++)
		for(int i=1;i<=n;i++)
			f[j][i]=f[j-1][f[j-1][i]];
	
	for(int i=1;i<=w;i++)
	{
		x=lca(l[i],r[i]);
		v[l[i]]++,v[r[i]]++;
		v[x]=v[x]-2;
	}
	
	for(int i=n;i;i--)
		v[f[0][q[i]]]=v[f[0][q[i]]]+v[q[i]];
	
	for(int i=2;i<=n;i++)
		if(v[i]%2==0)ans=(ans+z[id[i]])%mo;
	printf("%lld",ans);
	
	return 0;
}