记录编号	444099	评测结果	AAAAAAAAAA
题目名称	凯伦和超市	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.901 s
提交时间	2017-09-02 08:02:58	内存使用	383.50 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm> 
using namespace std;
const int maxn=5010;
long long n,m,b,c[maxn],d[maxn],x[maxn];
long long f[maxn][maxn][2];//dp[u][j][0]=min(dp[u][j-k][0],dp[v][k][0]) ??v?k?,?i-1??j-k?(???),u?????? ???????? k=0~sz[v]
int son[maxn];
vector<int>edge[maxn];
void dfs(int x){
	son[x]=1;
	f[x][0][0]=0;
	f[x][1][0]=c[x];//不用优惠券
	f[x][1][1]=c[x]-d[x];//用优惠券
	for(int k=0;k<(int)edge[x].size();k++){
		int p=edge[x][k];
		dfs(p);
		for(int i=son[x];i>=0;i--){
			for(int j=0;j<=son[p];j++){
				f[x][i+j][0]=min(f[x][i+j][0],f[x][i][0]+f[p][j][0]);
				f[x][i+j][1]=min(f[x][i+j][1],f[x][i][1]+f[p][j][1]);
				f[x][i+j][1]=min(f[x][i+j][1],f[x][i][1]+f[p][j][0]);
			}
		}
		son[x]+=son[p];
	}
}
int main(){
	freopen("market.in","r",stdin);
	freopen("market.out","w",stdout);
	scanf("%d%lld",&n,&b);
	memset(f,0x3f3f3f3f,sizeof(f));
	int t;
	scanf("%d%d",&c[1],&d[1]);
	for(int i=2;i<=n;i++){
		scanf("%d%d%d",&c[i],&d[i],&t);
		edge[t].push_back(i);
	}
	dfs(1);
	int ans;
	for(int i=n;i>=0;i--){
		if(f[1][i][0]<=b||f[1][i][1]<=b){
			ans=i;
			break;
		}
	}
	printf("%d\n",ans);
	return 0;
}