刷题记录表

#include<bits/stdc++.h>
using namespace std;
inline int read(int &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
struct tree{
	int next,ver;
} e[500010];
int head[500010],tot;
int n,m,q[500010];
int fa[500001],dep[500001],f[500001];
int ans,s,sx,sy;
void add(int a,int b){e[++tot].next=head[a],head[a]=tot,e[tot].ver=b;
e[++tot].next=head[b],head[b]=tot,e[tot].ver=a;}

void dfs(int x,int l)
{
	dep[x]=dep[l]+1;
	fa[x]=l;
	f[x]=(dep[l]%2)?1:-1;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].ver;
		if(y!=l)
		{
			if(dep[y])
			{
				sx=x,sy=y;
				continue;
			}
			dfs(y,x);
			f[x]+=f[y];
		}
	}
}

int main()
{
	freopen("namori.in","r",stdin);
	freopen("namori.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		read(a),read(b);
		add(a,b);
	}
	dfs(1,0);
	if(n-1==m)
	{
		if(f[1]!=0)
		{
			puts("-1");
			return 0;
		}
		for(int i=1;i<=n;i++) ans+=abs(f[i]);
	}
	else if((dep[sy]-dep[sx])%2==0)
	{
		if(f[1]%2!=0)
		{
			puts("-1");
			return 0;
		}
		s=-f[1]/2;
		ans=abs(s);
		for(;sx;sx=fa[sx]) f[sx]+=s;
		for(;sy;sy=fa[sy]) f[sy]+=s;
		for(int i=1;i<=n;i++) ans+=abs(f[i]);
	}
	else
	{
		if(f[1])
		{
			puts("-1");
			return 0;
		}
		int tp,mid;
		tp=0;
		for(;sy!=sx;sy=fa[sy])
		q[++tp]=f[sy],dep[sy]=0;
		sort(q+1,q+tp+1);
		mid=q[(tp+1)/2];
		ans=abs(mid);
		for(int i=1;i<=n;i++) if(dep[i]) ans+=abs(f[i]);
		for(int i=1;i<=tp;i++) ans+=abs(q[i]-mid);
	}
	printf("%d\n",ans);
	return 0;
}