[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;
}