3074 - 新家大采购
题目描述
金明一家搬到了新城市，为了方便，原来家里的东西没有搬过来，新家的东西都要重新采购。家里一共准备了 M 元钱，准备去大采购一番，把家里需要的物品采购齐全。
金明一家列出了想要购买的 N 件物品，编号为 1 \sim N，每件物品如果能买回来，都能为家人带来一定的愉快值，第 i 件物品的价格为 p_i 能给金明打来的愉快值为 v_i。
物品之间有一定的依赖关系，比如：如果要买墨水，就要买钢笔。要放钢笔，就得有笔筒。因此：墨水依赖了钢笔，钢笔依赖了笔筒，如果要买墨水必须保证钢笔和笔筒都买了，才能买墨水。也就是说，如果要买某物品，必须保证该物品依赖的所有物品都购买。
现给出 N 件物品之间的依赖关系，确保依赖关系能够将 N 件物品建成一棵树，请计算出金明通过本次大采购，能够给一家人带来的最大愉快值是多少？
输入
第 1 行读入 2 个整数 N,M。
接下来 N 行，第 i 行读入 3 个整数 p_i,v_i,r_i，表示编号为 i 的物品，价格为 p_i，能带来的愉快值为 v_i，该物品依赖于编号为 r_i 的物品。每个物品只有 1 件。
如果 r_i 的值为 -1，表示该物品不依赖任何其他的物品，数据保证这样的物品只有一件。
输出
输出最大愉快值。
样例
输入
5 30 10 35 4 11 5 5 5 12 1 12 59 2 4 2 -1
输出
66
输入
6 29 9 58 3 3 55 5 19 37 -1 15 85 3 5 24 4 18 86 2
输出
95
输入
7 23 10 53 5 18 88 7 16 29 5 8 52 -1 19 10 7 5 66 4 10 28 4
输出
146
说明
数据范围
对于所有的测试数据，满足 1 \le N,M \le 100，1 \le p_i,v_i \le 100。
来源
东方博宜OJ
标签
