#P2268. 「SDOI2017」苹果树

「SDOI2017」苹果树

题目描述

夏天近了,又到了恋爱的季节,小 Q 家门前的苹果树上结满了红红圆圆的苹果。

这株苹果树是一个有着 nn 个结点的有根树,其中结点被依次编号为 11nn11 号结点为根,其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果,第 ii 个结点上有 ai(ai>0)a_i (a_i > 0) 个苹果,每取走其中一个苹果就可以得到 vi(vi>0)v_i (v_i > 0) 的幸福度(若在这个结点取走 kaik \leq a_i 个苹果,则可以收获 kvikv_i 的幸福度)。如果在一个结点取走了至少一个苹果,则必须要在其父结点处取走至少一个苹果。

现在,给定正整数 kk,请从树上取走若干苹果。如果总计取走了 tt 个苹果,且所有取了至少一个苹果的那些结点的最大深度为 hh (这里规定根结点的深度为 11),则要求 thkt − h \leq k。问最大可以收获多少的幸福度?(这些幸福度全都归属于恋爱中的小 Q)

输入格式

本题有多组测试数据,输入的第一行给定整数 QQ 表示有 QQ 组数据。之后依次给出 QQ 组数据。
对于每一组数据来说,第一行包含两个整数 nnkk
之后 nn 行,每行给出三个整数,描述了每一个结点。其中第 ii 行的第一个整数给出了 ii 的父结点标号(如果 i=1i = 1,则其父结点为 00),第二个整数为 aia_i,第三个整数为 viv_i

输出格式

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

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%10\% 的数据,满足 nk3000000nk \leq 3\,000\,000 且给定的树的高度为 22
20%20\% 的数据,满足 nk25000000nk \leq 25\,000\,000 且给定的树的高度为 22
20%20\% 的数据,满足 nk25000000nk \leq 25\,000\,000 且所有 aia_i 均为 11
还有 20%20\% 的数据,满足 nk3000000nk \leq 3\,000\,000,没有上述额外限制。
对于 100%100\% 的数据,满足 1Q51 \leq Q \leq 51n200001 \leq n \leq 20\,0001k5000001 \leq k \leq 500\,0001nk250000001 \leq nk \leq 25\,000\,0001ai1081 \leq a_i \leq 10^81vi1001 \leq v_i \leq 100