| 比赛 |
果蝇王邀请赛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;
}