苹果树

题目描述:

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

输入格式:

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

样例输入:

(双击复制)

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

下载附加文件

提示:

有10%的数据，满足nk ≤ 3000000且给定的树的高度为2。
有20%的数据，满足nk ≤ 25000000且给定的树的高度为2。
有20%的数据，满足nk ≤ 25000000且所有ai均为1。
还有20%的数据，满足nk ≤ 3000000，没有上述额外限制。
对于100%的数据，满足1 ≤ Q ≤ 5; 1 ≤ n ≤ 20000; 1 ≤ k ≤ 500000; 1 ≤ nk ≤ 25000000; 1 ≤ ai ≤10⁸; 1 ≤ vi ≤ 100。

时间限制: 5000ms
空间限制: 512MB

---

来源: 山东省选2017day3t2