题解 AT2046 【Namori】
FlashHu
2019-03-04 21:53:16
神仙思维题还是要写点东西才好。
## 树
每次操作把相邻且同色的点反色，直接这样思考会发现状态有很强的后效性，没办法考虑转移。
因为树是二分图，所以我们转化模型：在树的奇数层的所有点上都有一枚棋子，每次可以将棋子移向相邻的空位，目标状态是树的偶数层的所有点上都有棋子。
这样的互换总次数有没有一个下界呢？
我们求出$a_i$表示点$i$子树中棋子数量与空位数量之差（可以是负数），那么$i$的父边就至少要交换$|a_i|$次。
为什么呢？子树里面空位比棋子少的话，肯定要通过父边把$a_i$个棋子送出去，才能移进来$a_i$个空位。反之亦然。
于是，如果$a_{rt}$（根）不为$0$就无解，否则$\sum\limits_{i=1}^n|a_i|$就是答案下界。
然后，仔细推一下发现它就是答案。
对于一个点，它的父边和所有子边的移进移出的顺序，和其它点的顺序是互相独立的。
等于说我们总能安排一个合法的顺序，使得它们一进一出一进一出。。。这样完整地衔接起来，而不会互相矛盾。
## 基环树
### 环长为偶数
显然的想法：把整个环当做根，不在环上的点的答案照算不误。所以把多出来一条边去掉做好树形DP。
首先这还是一个二分图，因此$a_{rt}$不为$0$同样无解。
于是，似乎这条边存在的意义只有分摊一部分转移、减少总次数了。
那么接下来要做的是，确定环上每条边的移动方向和次数。
设环长为$n$，$A_i$为以$i$为根求得的$a$值，$x_i$为环上第$i$条边的移动参数（正负表示方向，绝对值表示次数）
因为进出平衡，我们可以得到一个方程组
$$\begin{cases}x_1-x_2=A_1\\x_2-x_3=A_2\\...\\x_n-x_1=A_n\end{cases}$$
这时候我们发现上面那个方程组是没有唯一解的。那到底该分摊多少呢？
不着急，我们着眼于最小化$\sum|x_i|$，再把方程组整一整
$$\begin{cases}x_1=x_1-0\\x_2=x_1-A_1\\x_3=x_1-A_1-A_2\\...\\x_n=x_1-\sum_{i=1}^{n-1}A_i\end{cases}$$
每一行的$A$都是前缀和的形式，在树形DP的时候对应的是环上的每个点的$a$。
看到这儿就豁然开朗了。这不等于说，数轴上有若干个点取值分别为每一个$a$，找到一个点$x_1$使它到所有点距离之和最小？
把所有$a$排序，$x_1$不就可以取第$\frac n 2$大的数到第$\frac n 2+1$大的数之间的任意整数么？
最后把环上的DP值改一改就OK了。
### 环长为奇数
因为不是二分图了，所以直接解方程好像做不下去。我们从更直观的意义来理解它。
仍然是去掉一条边做树形DP。这时候我们看看，在这条非树边上操作，在奇偶染色模型下等价于什么呢？
没错，两个棋子会在这里同时变成空位，两个空位会在这里同时变成棋子！
那这条边存在的意义，是把棋子或空位中多的减掉、少的补上。要操作多少次呢？$\frac{\sum A_i}{2}$，在树形DP中对应的是$\frac{a_{rt}}{2}$。
注意如果$a_{rt}$是奇数那么无解。否则环底部的$A$发生了变化，导致要把环上的$a$都减掉$\frac{a_{rt}}{2}$。
---
最后的最后扫一遍数组统计答案。代码没有任何难点。
```cpp
#include<bits/stdc++.h>
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
const int SZ=1<<19,N=1e5+9,M=2*N;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int he[N],ne[M],to[M],f[N],a[N],b[N];
int Getf(R x){
return x==f[x]?x:f[x]=Getf(f[x]);
}
void Dfs(R x,R op){
a[x]=op;
for(R y,i=he[x];i;i=ne[i])
if((y=to[i])!=f[x])
f[y]=x,Dfs(y,-op),a[x]+=a[y];
}
int main(){
R n=in(),m=in(),rt=1,re=1,p=0,ans=0;
for(R i=1;i<=n;++i)f[i]=i;
for(R p=0,i=1;i<=m;++i){
R x=in(),y=in();
if(Getf(x)!=Getf(y))f[f[x]]=f[y];
else{rt=x,re=y;continue;}//把多的边单独拿出来
ne[++p]=he[x];to[he[x]=p]=y;
ne[++p]=he[y];to[he[y]=p]=x;
}
f[rt]=0;Dfs(rt,1);
if(n==m){//基环树
for(R x=re;x;x=f[x])b[++p]=a[x];
if(p&1){//奇环
if(a[rt]&1)return puts("-1"),0;
for(R x=re;x;x=f[x])a[x]-=a[rt]>>1;
}
else{//偶环
if(a[rt])return puts("-1"),0;
sort(b+1,b+p+1);
for(R x=re;x;x=f[x])a[x]-=b[p>>1];
}
}//树
else if(a[rt])return puts("-1"),0;
for(R i=1;i<=n;++i)ans+=abs(a[i]);
return cout<<ans<<endl,0;
}
```