P1552 [APIO2012] 派遣

题目描述

给出一棵 $N$ 个点的树，每个点有三个属性：父亲节点编号 $B_i$、薪水$C_i$、领导力$L_i$。

可以让一个点当领导，然后在这个点的子树中选择一些费用和不超过 $M$ 的点，定义满意度为：领导的领导力 乘 选择的点的个数（领导可不被选择）。

求满意度的最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$。

下来 $N$ 行。第 $i$ 行包含三个整数 $B_i,C_i,L_i$ 分别表示第 $i$ 个点的上级，薪水以及领导力。树根满足 $B_i=0$，并且每一个点的父亲节点编号一定小于自己的编号 $B_i\lt i$。

输出格式

一行一个整数，表示满意度的最大值。

输入输出样例 #1

输入 #1

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

输出 #1

6

说明/提示

$1 \le N \le 10^5$，$1 \le M \le 10^9$，$0 \le B_i \lt i$，$1 \le C_i \le M$，$1 \le L_i \le 10^9$。

对于 $30\%$ 的数据，$N \le 3000$。