Submission #2125987

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,head[MN+5],cnt=1,ans=0,f[MN+5],g[MN+5][2],Fa[MN+5],dep[MN+5],A,B,C,c[MN+5],num,mn=1e9;
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
    e[++cnt]=(edge){t,head[f]};head[f]=cnt;
    e[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
inline int Abs(int x){return x<0?-x:x;}
void dfs(int x,int fa=0)
{
    ++g[x][f[x]];
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            if(x==A&&e[i].to==B) continue;
            if(x==B&&e[i].to==A) continue;
            f[e[i].to]=f[x]^1;dfs(e[i].to,x);
            g[x][0]+=g[e[i].to][0];
            g[x][1]+=g[e[i].to][1];
        }
    ans+=Abs(g[x][0]-g[x][1]);
}
void FindCircle(int x,int fa)
{
    Fa[x]=fa;
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            if(dep[e[i].to]) A=x,B=e[i].to;
            else dep[e[i].to]=dep[x]+1,FindCircle(e[i].to,x);
        }
}
int Solve(int x)
{
    int res=Abs(x);
    for(int s=A;s!=C;s=Fa[s]) g[s][0]+=x;
    for(int s=B;s!=C;s=Fa[s]) g[s][1]+=x;
    for(int i=1;i<=n;++i) res+=Abs(g[i][0]-g[i][1]);
    for(int s=A;s!=C;s=Fa[s]) g[s][0]-=x;
    for(int s=B;s!=C;s=Fa[s]) g[s][1]-=x;
    return mn=min(mn,res),res;
}
int main()
{
    n=read();m=read();if(n&1) return 0*puts("-1");
    if(m<n)
    {
        for(int i=1;i<n;++i) ins(read(),read());
        dfs(1);
        printf("%d\n",g[1][0]==g[1][1]?ans:-1);
    }
    else
    {
        for(int i=1;i<=n;++i) ins(read(),read());
        FindCircle(dep[1]=1,0);
        for(int x=A,y=B;x!=y;C=x=Fa[x])
            if(dep[x]<dep[y]) swap(x,y);
        for(int i=A;i!=C;i=Fa[i]) c[++num]=i;
        c[++num]=C;int len=dep[A]+dep[B]-2*dep[C]+1;num=len;
        for(int i=B;i!=C;i=Fa[i]) c[len--]=i;
        dfs(1);
        if(num&1) printf("%d\n",ans+Abs(g[1][0]-g[1][1])/2);
        else
        {
            if(g[1][0]!=g[1][1]) return 0*puts("-1");
            int l=-n,r=n;
            while(r-l+1>2)
            {
                int m1=l+(r-l+1)/3,m2=m1+(r-l+1)/3;
                int res1=Solve(m1),res2=Solve(m2);
                if(res1<res2) r=m2-1;
                else l=m1+1;
            }
            while(l<=r) Solve(l++);
            printf("%d\n",mn);
        }
    }
    return 0;
}

Submission Info

Judge Result