/ Vijos / 题库 /

小Q的苹果树

小Q的苹果树

描述

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

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

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

格式

输入格式

本题有多组测试数据,输入的第一行给定整数\(Q\)表示有\(Q\)组数据。之后依次给出\(Q\)组数据。

对于每一组数据来说,第一行包含两个整数\(n\) 和\(k\)。
之后\(n\)行,每行给出三个整数,描述了每一个结点。其中第\(i\)行的第一个整数给出了\(i\)的父结点标号(如果\(i = 1\),则其父结点为\(0\)),第二个整数为\(a_i\),第三个整数为\(v_i\)。

输出格式

输出一共有\(Q\)行,对应了\(Q\)组数据。

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

样例1

样例输入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\le 3000000\)且给定的树的高度为\(2\)。

有20%的数据,满足\(nk\le 25000000\)且给定的树的高度为\(2\)。

有20%的数据,满足\(nk\le 25000000\)且所有\(a_i\)均为\(1\)。

还有20%的数据,满足\(nk\le 3000000\),没有上述额外限制。

对于100%的数据,满足\(1\le Q\le 5\); \(1\le n\le 20000\); \(1\le k\le 500000\); \(1\le nk\le 25000000\); \(1\le a_i\le 10^8\); \(1\le v_i\le 100\)。

来源

SDOI 2017 Round2 Day1

信息

ID
2020
难度
7
分类
(无)
标签
递交数
27
已通过
6
通过率
22%
上传者

相关

在下列训练计划中:

RP++分类题库