[??记录]AT2046 [AGC004F] Namori

**题意** ： 给出一张 $n$ 个点 $m$ 条边的连通图，满足 $n-1\leq m\leq n$。 初始时每个点都是白色，每次操作可以选择一条边，若两个端点的颜色相同，则可以将两个端点的颜色取反。 目标是将所有点变为黑色，求出所需的最小步数，或指出无解。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ - $n$ 为奇数时无解 每个点最终一定参与了奇数次操作，$n$ 个奇数求和，得到奇数次对点的影响。 一次操作影响 $2$ 个点，对点的影响只可能是偶数次，矛盾。 - $n$ 为偶数，且图是一棵树 注意到树是二分图，将树黑白染色，操作能进行的条件就变为“端点异色”，且作用等价于将黑点移动一步。 目标是将黑白位置对调。 操作只能移动，不能改变黑白点的个数。由此可以发现，若黑白染色后，两种颜色的点不相同，则必然无解，否则有解。  考虑某个子树连向父亲的边，若子树内有 $a$ 个黑点，以及 $b$ 个白点，那么该边至少要用于向内或向外运输 $|a-b|$ 个黑点。可以归纳证明这同时也是可以取到的。 具体地，将黑点的点权置为 $+1$ ，白点的点权置为 $-1$ ，记 $u$ 的子树点权和为 $c_u$ ，则答案为 $\sum\limits_{i=1}^n|c_i|$。 - $n$ 为偶数，且图是一棵基环树，环长为偶数 此时图仍然是二分图，前面的转化仍然成立。 在环上断掉一条边，看做树的情况，然后单独考虑该边的使用次数。 若按照指定方向使用了 $x$ 次，则对 $c$ 的影响如下 ：  将会受到影响的点的贡献写成 $\sum|w_i-x|$ 的形式，即转化为经典问题。 - $n$ 为偶数，且图是一棵基环树，环长为奇数 此时图不再是二分图了。 先断掉一条环上的边，然后黑白染色。 这条特殊的边使用规则和其他边不同，每次可以把黑黑变为白白，或者白白变为黑黑。 查看整棵树的权值和 $c_{rt}$ ，若为偶数，则可以利用这条边消除之，否则无解。 而这条边的使用次数也可以恰好为 $|c_{rt}|/2$ ，证明略去。 考虑完这条边的影响后，完全转化为树的情况。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define MaxN 100500 using namespace std; struct UFS{ int f[MaxN]; void Init(int n) {for (int i=1;i<=n;i++)f[i]=i;} int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} bool merge(int u,int v){ u=find(u);v=find(v); if (u==v)return 0; f[u]=v;return 1; } }T; vector<int> g[MaxN]; void adl(int u,int v) {g[u].pb(v);g[v].pb(u);} int f[MaxN],c[MaxN];bool e[MaxN]; void dfs(int u,int fa,bool fl) { e[u]=fl;f[u]=fa; if (fl)c[u]=1;else c[u]=-1; for (int i=0;i<g[u].size();i++) if (g[u][i]!=fa){ dfs(g[u][i],u,!fl); c[u]+=c[g[u][i]]; } } int n,m,a[MaxN],ans,w[MaxN]; int lca(int u,int v) { for (int i=1;i<=n;i++)e[i]=0; for (int p=u;p;p=f[p])e[p]=1; while(!e[v])v=f[v]; return v; } int main() { scanf("%d%d",&n,&m); if (n&1){puts("-1");return 0;} if (m==n-1){ for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); adl(u,v); } dfs(1,0,1); if (c[1]!=0){puts("-1");return 0;} for (int i=1;i<=n;i++) ans+=(c[i]<0 ? -c[i] : c[i]); printf("%d",ans); }else { T.Init(n); int u0,v0; for (int i=1,u,v;i<=n;i++){ scanf("%d%d",&u,&v); if (T.merge(u,v))adl(u,v); else {u0=u;v0=v;} }dfs(1,0,1); if (e[u0]==e[v0]){ if (c[1]%2){puts("-1");return 0;} int d=c[1]/2;ans+=(d<0 ? -d : d); for (int u=u0;u;u=f[u])c[u]-=d; for (int u=v0;u;u=f[u])c[u]-=d; for (int i=1;i<=n;i++) ans+=(c[i]<0 ? -c[i] : c[i]); printf("%d",ans); }else { if (c[1]!=0){puts("-1");return 0;} int tn=0,t=lca(u0,v0); for (int u=u0;u!=t;u=f[u]){w[++tn]=c[u];c[u]=0;} for (int u=v0;u!=t;u=f[u]){w[++tn]=-c[u];c[u]=0;} w[++tn]=0; for (int i=1;i<=n;i++) ans+=(c[i]<0 ? -c[i] : c[i]); nth_element(w+1,w+tn/2,w+tn+1); for (int i=1;i<=tn;i++) ans+=(w[tn/2]<=w[i] ? w[i]-w[tn/2] : w[tn/2]-w[i]); printf("%d",ans); } }return 0; } ```