记录编号	590914	评测结果	AWAWWWWWWW
题目名称	喵星人集会	最终得分	20
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	0.044 s
提交时间	2024-07-12 18:16:12	内存使用	3.71 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,idx,maxz,ans=LONG_LONG_MAX;
ll k[205],a[205],f[205][205];
ll hd[205],nxt[205],ed[205];
string s;
void build(int x,int y){
    nxt[++idx]=hd[x];
    hd[x]=idx;
    ed[idx]=y;
}
void dfs(int now,int p){
    if(a[now]==1)k[now]++;
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
        if(y!=p){
            dfs(y,now);
            k[now]+=k[y];
        }
    }
}
void dp(int now,int p){
//    cout<<now<<" "<<p<<endl;
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
        if(y!=p){
            dp(y,now);
            f[now][0]+=f[y][0]+k[y];
            f[now][1]=f[now][0];
        }
    }
//    cout<<"now:"<<now<<" "<<f[now][0]<<" "<<f[now][1]<<" ";
    for(int i=2;i<=k[now];i++){
        int o=i-1;
        f[now][i]=1-a[now];
        for(int j=hd[now];j;j=nxt[j]){
            int y=ed[j];
            if(y!=p){
                if(o>k[y]){
                    f[now][i]+=f[y][k[y]];
                    o-=k[y];
                }else{
                    f[now][i]+=f[y][o]+k[y]-o;
                    o=0;
                }
            }
        }
//        cout<<f[now][i]<<" ";
    }
    f[now][0]=f[now][1];
//    cout<<endl;
}
int main(){
    freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        a[i+1]=s[i]-'0';
        maxz+=a[i+1];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        build(x,y);
        build(y,x);
    }
//    dfs(1,1);
    for(int i=1;i<=n;i++){
        dfs(i,i);
        dp(i,i);
//        cout<<f[i][maxz]<<endl;
        ans=min(ans,f[i][maxz]);
        memset(f,0,sizeof(f));
        memset(k,0,sizeof(k));
    }
    cout<<ans;
    return 0;
}