[SDOI2017] 苹果树

题目背景

#警告:滥用本题评测将封号

题目描述

夏天近了,又到了恋爱的季节,小Q家门前的苹果树上结满了红红圆圆的苹果。 这株苹果树是一个有着$n$个结点的有根树,其中结点被依次编号为$1$至$n$。$1$号结点为根,其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果,第$i$个结点上有$a_i (a_i > 0)$个苹果,每取走其中一个苹果就可以得到$v_i (v_i > 0)$的幸福度(若在这个结点取走$k \leq a_i$个苹果,则可以收获$kv_i$的幸福度)。如果在一个结点取走了至少一个苹果,则必须要在其父结点处取走至少一个苹果。 现在,给定正整数$k$,请从树上取走若干苹果。如果总计取走了$t$个苹果,且所有取了至少一个苹果的那些结点的最大深度为$h$(这里规定根结点的深度为$1$),则要求$t-h \leq k$。问最大可以收获多少的幸福度?(这些幸福度全都归属于恋爱中的小Q。)

输入输出格式

输入格式


本题有多组测试数据,输入的第一行给定整数$Q$,表示有$Q$组数据。之后依次给出$Q$组数据。 对于每一组数据来说,第一行包含两个整数$n$和$k$。 之后$n$行,每行给出三个整数,描述了每一个结点。其中第$i$行的第一个整数给出了$i$的父结点标号 (如果$i = 1$,则其父结点为$0$),第二个整数为$a_i$,第三个整数为$v_i$。

输出格式


输出一共有$Q$行,对应了$Q$组数据。 对于每一组数据,输出一个整数,表示最大可以收获的幸福度。

输入输出样例

输入样例 #1

2
5 1
0 1 1
1 1 1
1 1 3
2 1 10
3 1 4
9 15
0 1 1
1 7 2
2 5 10
1 3 1
4 3 17
4 3 18
4 4 19
1 1 1
8 1 100

输出样例 #1

15
316

说明

有$10\%$的数据,满足$nk \leq 3000000$且给定的树的高度为$2$。 有$20\%$的数据,满足$nk \leq 25000000$且给定的树的高度为$2$。 有$20\%$的数据,满足$nk \leq 25000000$且所有$a_i$均为$1$。 还有$20\%$的数据,满足$nk \leq 3000000$,没有上述额外限制。 对于$100\%$的数据,满足$1 \leq Q \leq 5$;$1 \leq n \leq 20000$;$1 \leq k \leq 500000$;$1 \leq nk \leq 25000000$;$1 \leq a_i \leq 10^8$;$1 \leq v_i \leq 100$。