AGC004F Namori

AtCoder
Luogu翻译

分析

神仙题。大力分类讨论论论。

树

给奇数层的点染成白色，偶数层的点染成黑色。
现在问题变成，每次可以交换两个相邻的不同色的点，要让所有黑点变白、白点变黑。
显然，如果黑点数和白点数不同，则无解。
设白点的权值为$1$，黑点的权值为$-1$，$sum[i]$表示子树中的权值和，那么答案为$\sum\limits_{i=1}^n |sum[i]|$。
证明不会，感性理解一下即可。

奇环

可以看做树多了一条边。继续沿用上面的黑白色，那么多的那条边的两个端点颜色一定相同。
那么对这条边操作一次的话，黑与白的差会改变$2$。
显然，如果差是奇数的话，无解。
于是我们直接利用这条边，把黑与白的差补成$0$就行了。
然后就是树的情况了。

偶环

此时多出来的那条边的两个端点的颜色不同。
假设这条边用了$w$次。那么其中一个点的到$\mathrm{LCA}$的$sum$要加上$w$，另一边要减掉$w$。
此时的答案是不受影响的点权的绝对值之和，加上$\sum\limits_{i}|w-k[i]\times sum[i]|$。
显然后面一部分当$w$取中位数会最优，于是就做完了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;

struct Edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

namespace task1 {
    int s,c[N],sum[N];
    inline void dfs(int u,int fa) {
        sum[u]=c[u],s+=c[u];
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            c[v]=-c[u],dfs(v,u),sum[u]+=sum[v];
        }
    }
    
    inline void work() {
        c[1]=1,dfs(1,0);
        if (s) { puts("-1"); return; }
        int ans=0;
        for (re int i=1;i<=n;++i) ans+=abs(sum[i]);
        printf("%d\n",ans);
    }
}

namespace task2 {
    int c[N],sum[N],fa[N];
    int s,isodd,st,ed;
    
    namespace odd {
        inline void work() {
            if (s&1) { puts("-1"); return; }
            int dlt=s/2,ans=abs(dlt);
            for (re int i=st;i;i=fa[i]) sum[i]-=dlt;
            for (re int i=ed;i;i=fa[i]) sum[i]-=dlt;
            for (re int i=1;i<=n;++i) ans+=abs(sum[i]);
            printf("%d\n",ans);
        }
    }

    namespace even {
        int tmp[N],mark[N],w;
        inline void work() {
            if (s) { puts("-1"); return; }
            int top=0;
            for (re int i=ed;i!=st&&i;i=fa[i])
                tmp[++top]=sum[i],mark[i]=1;
            sort(tmp+1,tmp+top+1);
            if (top&1) w=tmp[(top+1)/2];
            else w=(tmp[top/2]+tmp[top/2+1])/2;
            int ans=abs(w);
            for (re int i=1;i<=n;++i) {
                if (mark[i]) ans+=abs(sum[i]-w);
                else ans+=abs(sum[i]);
            }
            printf("%d\n",ans);
        }
    }

    inline void dfs(int u,int f) {
        sum[u]=c[u],s+=c[u],fa[u]=f;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==f) continue;
            if (c[v]) {
                if (c[u]==c[v]) isodd=1;
                st=u,ed=v;
            }
            else c[v]=-c[u],dfs(v,u),sum[u]+=sum[v];
        }
    }
    
    inline void work() {
        c[1]=1,dfs(1,0);
        if (isodd) odd::work();
        else even::work();
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    if (m==n-1) task1::work();
    else task2::work();
    return 0;
}