[AGC034E] Complete Compress
考虑这道题之前，我们先想一个经典问题：
对于一颗有根树，每个节点上可能放一颗棋子，且不同子树上的棋子可以相互抵消。那么，我们设maxson为最大子树包含的棋子数，sun【root】为root的所有子树的棋子总数，很容易得到，如果sum【root】-maxson>=maxson，那么它们一定可以相互抵消，否则不能。（所以sum【root】必需为奇数）
回到本题，看到N的范围不大，我们可以考虑换根，即枚举每一个节点为根。
可以证明让含有祖先关系的两个节点相互靠近是无用功，因此我们只需考虑将不同子树上的节点抵消。
而对于u节点，若有棋子，则可以将一个棋子拆为dis（u，root）个棋子，那么原题就转化为了上面的经典问题。（下文的棋子均指拆开后的棋子）
设f【x】表示消去以x的子树内的棋子，所需的最小步数。设maxp为最大儿子节点编号，max为最大儿子节点上的棋子个数。和经典问题一样，分两种情况讨论。
记得每次换根的时候清零sum
如果f【root】==sum【root】/2，则答案合法。（代码实现的时候，还要判一下sum【root】的奇偶性）
#include<bits/stdc++.h> using namespace std; const int N=4e3+33; const int inf=2e9+555; typedef long long ll; char c; int n,cnt,head[N],a[N],siz[N],sum[N],f[N],root,ans; struct edge{ int to,nex; }e[N]; void adda(int u,int v){ e[++cnt].to=v;e[cnt].nex=head[u];head[u]=cnt; } void dfs(int u,int fa){ if(a[u]) siz[u]=1; else siz[u]=0; int maxp=0; for(int i=head[u];i;i=e[i].nex){ int v=e[i].to; if(v==fa) continue; dfs(v,u); siz[u]+=siz[v]; sum[u]+=sum[v]+siz[v]; if(sum[v]+siz[v]>sum[maxp]+siz[v]) maxp=v; } int maxson=sum[maxp]+siz[maxp]; if(sum[u]-maxson>=maxson) f[u]=sum[u]/2; else f[u]=sum[u]-maxson+min(f[maxp],maxson-sum[u]/2); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>c; if(c=='1') a[i]=1; } for(int i=1,u,v;i<n;i++){ cin>>u>>v; adda(u,v);adda(v,u); } ans=inf; for(int i=1;i<=n;i++){ memset(sum,0,sizeof(sum)); root=i; dfs(root,0); if(f[root]==sum[root]/2&&sum[root]%2==0) ans=min(ans,f[root]); } if(ans==inf) cout<<-1; else cout<<ans; return 0; }