815C - Karen and Supermarket - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int n,m;
int c[N],d[N],x;
vector<int> g[N];
int dp[N][N][2];
int siz[N];
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&c[i],&d[i]);
		if(i>=2){
			scanf("%lld",&x);
			g[x].push_back(i);
		}
	}
	for(int x=n;x>=1;x--){
		memset(dp[x],0x3f,sizeof dp[x]);
		dp[x][0][0]=dp[x][0][1]=0;
		dp[x][1][0]=c[x],dp[x][1][1]=c[x]-d[x];
		siz[x]=1;
		int l=g[x].size();
		for(int j=0;j<l;j++){
			int y=g[x][j];
			for(int k=siz[x];k>=0;k--){
				for(int l=siz[y];l>=0;l--){
					dp[x][k+l][0]=min(dp[x][k+l][0],dp[x][k][0]+dp[y][l][0]);
					if(k){
						dp[x][k+l][1]=min(dp[x][k+l][1],dp[x][k][1]+dp[y][l][1]);
					}
				}
			}
			siz[x]+=siz[y];
		}
		for(int j=0;j<=siz[x];j++){
			dp[x][j][1]=min(dp[x][j][1],dp[x][j][0]);
		}
	}
	for(int i=n;i>=0;i--){
		if(dp[1][i][1]<=m){
			printf("%lld",i);
			return 0;
		}
	}
	return 0;
}//