记录编号	444076	评测结果	AAAAAAAAAA
题目名称	2747.凯伦和超市	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	2.257 s
提交时间	2017-09-01 22:04:01	内存使用	383.43 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=5000+10;
long long minn[maxn][maxn][2];
vector<int>A[maxn];
int v[maxn],c[maxn];
int size[maxn];
int n;
inline void dfs(int x){
	size[x]=1;
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		dfs(u);
		for(int j=size[x];j>=0;j--){
			for(int k=0;k<=size[u];k++){
				minn[x][j+k][1]=min(minn[x][j+k][1],min(minn[u][k][1],minn[u][k][0])+minn[x][j][1]);
				minn[x][j+k][0]=min(minn[x][j+k][0],minn[u][k][0]+minn[x][j][0]);
			}
		}
		size[x]+=size[u];
	}
	for(int i=n-1;i>=0;i--){
		minn[x][i+1][1]=minn[x][i][1]+v[x]-c[x];
		minn[x][i+1][0]=min(minn[x][i][0]+v[x],minn[x][i+1][0]);
	}
}
int main(){
	freopen("market.in","r",stdin);
	freopen("market.out","w",stdout);
	memset(minn,127/2,sizeof(minn));
	long long b;
	cin>>n>>b;
	for(int i=1;i<=n;i++)
		minn[i][0][1]=minn[i][0][0]=0;
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d %d",&v[i],&c[i]);
		if(i>=2){
			scanf("%d",&x);
			A[x].push_back(i);
		}
	}
	dfs(1);
	int ans=0;
	for(int j=1;j<=n;j++)
		if((minn[1][j][1]<=b||minn[1][j][0]<=b)&&j>ans)
			ans=j;
	printf("%d",ans);
	/*for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			printf("%d ",minn[i][j][0]);
		}
		puts("");
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			printf("%d ",minn[i][j][1]);
		}
		puts("");
	}*/
return 0;
}