简单的线性dp。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{int i,j,k,n,m;int p[2001];int c[2001];int e[2001];int dp[2001][201];memset(dp,0,sizeof(dp));cin>>n>>m;for(i=2;i<=n;i++)cin>>p[i];for(i=1;i<=n;i++)cin>>c[i];for(i=1;i<=n;i++)cin>>e[i];for(i=n;i>=1;i--){for(j=m;j>=c[i];j--){dp[i][j]=max(dp[i][j],e[i]);}for(j=m;j>=0;j--){for(k=0;k<=j;k++){dp[p[i]][j]=max(dp[p[i]][j],dp[p[i]][j-k]+dp[i][k]);}}}int mm;mm=0;for(i=0;i<=m;i++){if(mm<dp[1][i])mm=dp[1][i];}cout<<mm<<endl;return 0;
}