记录编号	444995	评测结果	AAAAAAAAAA
题目名称	2747.凯伦和超市	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	0.780 s
提交时间	2017-09-04 20:33:25	内存使用	195.01 MiB

#include <cstdio>
#include <vector>

using namespace std;

#define N 5050
#define INF 99999999

int c[N], d[N], x[N], n, size[N], f[N][N] = {0}, g[N][N] = {0};
vector<int> vec[N];

int min(int a, int b)
{
	if(a > b)
	{
		return b;
	}
	return a;
}
int max(int a, int b)
{
	if(a > b)
	{
		return a;
	}
	return b;
}
void dfs(int a)
{
	int x = vec[a][0];
	size[a] = 1;
	for(int i = 1; i <= n; i++)
	{
		f[a][i] = g[a][i] = INF;
	}
	f[a][1] = c[a];
	g[a][0] = g[a][1] = c[a] - d[a];
	for(int i = 1; i <= x; i++)
	{
		int v = vec[a][i];
		dfs(v);
		for(int j = size[a]; j >= 0; j--)
		{
			for(int k = 1; k <= size[v]; k++)
			{
				f[a][j + k] = min(f[a][j + k], f[a][j] + f[v][k]);
				g[a][j + k] = min(g[a][j + k], g[a][j] + min(g[v][k], f[v][k]));
			}
		}
		size[a] += size[v];
	}
	return;
}
int main()
{	
	int b, ans = 0;
	freopen("market.in", "r", stdin);
	freopen("market.out", "w", stdout);
	
	scanf("%d%d", &n, &b);
	
	scanf("%d %d", &c[1], &d[1]);
	
	x[1] = 0;
	for(int i = 1; i <= n; i++)
	{
		vec[i].push_back(0);
	}
	for(int i = 2; i <= n; i++)
	{
		
		scanf("%d%d%d", &c[i], &d[i], &x[i]);
		
		vec[x[i]].push_back(i);
		vec[x[i]][0]++;
	}
	dfs(1);
	for(int i = 1; i <= n; i++)
	{
		if(g[1][i] <= b||f[1][i] <= b)
		{
			ans = i;
		}
	}
	
	printf("%d\n", ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}