记录编号	445053	评测结果	AAAAAAAAAA
题目名称	凯伦和超市	最终得分	100
用户昵称	サイタマ	是否通过	通过
代码语言	C++	运行时间	0.753 s
提交时间	2017-09-04 21:39:47	内存使用	191.97 MiB

#include <algorithm>
#include   <cstdlib>
#include    <cstdio>
#include    <vector>
#include     <ctime>
#include     <cmath>
#define INF (1<<30)-1
#define MAXN 5010
namespace IO {
	char buf[1 << 15], *fs, *ft;
	inline char gc() { return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? 0 : *fs++; }
	inline int qr() {
		int x = 0, ch = gc();
		while (ch<'0' || ch>'9') { ch = gc(); }
		while (ch >= '0'&&ch <= '9') { x = (x << 1) + (x << 3) + ch - '0';ch = gc(); }
		return x;
	}
}using namespace IO;
using namespace std;
/*************************************************************************************************************************/
vector<int>mp[MAXN];
int N, M, h[MAXN], siz[MAXN], c[MAXN], d[MAXN], f[MAXN][MAXN], g[MAXN][MAXN];
//f[i][j]表示以i为根的子树中购买j个商品且必须用第i张优惠券的最小花费
//g[i][j]表示以i为根的子树中购买j个商品不使用优惠券的最小花费
void DFS(int u) {
	int v;
	siz[u] = 1;
	for (int i = 1;i <= N;i++)f[u][i] = g[u][i] = INF;
	f[u][1] = c[u] - d[u];g[u][1] = c[u];g[u][0] = 0;
	for (register int i = 0;i < (int)mp[u].size();i++) {
		v = mp[u][i];
		DFS(v);
		for (register int j = 1;j <= siz[u];j++)h[j] = f[u][j];
		for (register int j = 1;j <= siz[u];j++) {
			for (register int k = 1;k <= siz[v];k++) {
				f[u][j + k] = min(f[u][j + k], h[j] + min(f[v][k], g[v][k]));
			}
		}
		for (register int j = 0;j <= siz[u];j++)h[j] = g[u][j];
		for (register int j = 0;j <= siz[u];j++) {
			for (register int k = 1;k <= siz[v];k++) {
				g[u][j + k] = min(g[u][j + k], h[j] + g[v][k]);
			}
		}
		siz[u] += siz[v];
	}
}
int main() {
	freopen("market.in", "r", stdin);
	freopen("market.out", "w", stdout);
	int x;
	N = qr();M = qr();
	c[1] = qr();d[1] = qr();
	for (register int i = 2;i <= N;i++) {
		c[i] = qr();d[i] = qr();x = qr();
		mp[x].push_back(i);
	}
	DFS(1);
	int ans;
	for (ans = 1;ans <= N;ans++) {
		if (min(f[1][ans], g[1][ans]) > M)break;
	}
	printf("%d", ans - 1);
	return 0;
}