4290: 「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$ 组数据。 对于每一组数据，输出一个整数，表示最大可以收获的幸福度。

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

15
316