比赛 果蝇王邀请赛div1 评测结果 WWWWWWWWWWWWWWWWWWWW
题目名称 蜜雪冰城甜蜜蜜 最终得分 0
用户昵称 运行时间 7.391 s
代码语言 C++ 内存使用 8.20 MiB
提交时间 2026-08-27 12:59:53
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (int)(1e18)

const int N=702;

int n;
int fa[N],w[N];

vector<int> g[N];
vector<vector<int>> dp[N];

inline int read(){
    int t=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
    while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
    return t*f;
}

int dep[N],maxl[N],siz[N];

void Min(int &x,int y){x=x<y?x:y;}

void merge(int u,int dao){
    vector<vector<int>> tmp(siz[u]+siz[dao]+1,vector<int>(maxl[u]+1,INT_MAX));
    for(int i=0;i<=siz[u];i++){
        for(int j=0;j<=siz[dao];j++){
            // Min(tmp[i+j][0],dp[u][i][0]+dp[dao][j][0]);
            for(int len=1;len<=maxl[u];len++)
                Min(tmp[i+j][len],dp[u][i][len]+dp[dao][j][len-1]);
        }
    }
    siz[u]+=siz[dao];
    dp[u].resize(siz[u]+1);
    for(int i=0;i<=siz[u];i++){
        dp[u][i].resize(maxl[u]+1,INT_MAX);
        for(int j=0;j<=maxl[u];j++)
            dp[u][i][j]=tmp[i][j];
    }
}

void dfs(int u,int v){
//    cout<<"u:"<<u<<"\n";
    dep[u]=dep[v]+1,siz[u]=1,maxl[u]=1;
    dp[u].resize(siz[u]+1);
    for(int i=0;i<=siz[u];i++) dp[u][i].resize(maxl[u]+1,INT_MAX);
    for(int i=0;i<=0;i++) dp[u][i][0]=0;
    for(int dao:g[u]){
        dfs(dao,u);
        maxl[u]=max(maxl[u],maxl[dao]+1);
        for(int i=0;i<=siz[u];i++){
            dp[u][i].resize(maxl[u]+1,INT_MAX);
            for(int j=1;j<=maxl[u];j++) Min(dp[u][i][j],dp[u][i][j-1]);   
        }
        for(int i=0;i<=siz[dao];i++){
            dp[dao][i].resize(maxl[u],INT_MAX);
            for(int j=1;j<maxl[u];j++) Min(dp[dao][i][j],dp[dao][i][j-1]);   
        }
        merge(u,dao);
        vector<vector<int>> _;
        swap(_,dp[dao]);
    }
    for(int i=0;i<=siz[u];i++)
        for(int j=1;j<=maxl[u];j++)
            Min(dp[u][i+max(0ll,j-i)][0],dp[u][i][j]+maxl[u]*max(0ll,j-i));
    // vector<int> minn(maxl[u]+1,INT_MAX);
    // for(int i=0;i<=siz[u];i++){
    //     for(int j=0;j<=maxl[u];j++){
    //         //Min(dp[u][i][j],dp[u][i1][j]+(i-i1)*dep_u)
    //         Min(dp[u][i][j],minn[j]+i*w[dep[u]]);
    //         Min(minn[j],dp[u][i][j]-i*w[dep[u]]);
    //     }
    // }
    // for(int i=1;i<=maxl[u];i++)
    //     for(int j=i+1;j<=siz[u];j++)
    //         Min(dp[u][j][0],dp[u][j][i]);
}

signed main(){
    freopen("sweet.in","r",stdin);
    freopen("sweet.out","w",stdout);
    n=read();
    for(int i=2;i<=n;i++) fa[i]=read(),g[fa[i]].push_back(i);
    for(int i=1;i<=n;i++) w[i]=read();
    dfs(1,0);
    int ans=INT_MAX;
    for(int i=1;i<=n;i++) Min(ans,dp[1][i][0]);
    cout<<ans<<"\n";
    return 0;
}