比赛场次 553
比赛名称 2022级DP专题练习赛3
比赛状态 已结束比赛成绩
开始时间 2023-02-17 18:30:00
结束时间 2023-02-17 22:00:00
开放分组 全部用户
注释介绍 以赛代练
题目名称 苹果树
输入输出 sdoi2017_apple.in/out
时间限制 5000 ms (5 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

苹果树

★★★★   输入文件:sdoi2017_apple.in   输出文件:sdoi2017_apple.out   简单对比
时间限制:5 s   内存限制:512 MiB

【题目描述】

夏天近了,又到了恋爱的季节,小 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

【样例2】

点击下载样例2

【数据规模与约定】

有 $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$。

【来源】

SDOI 2017