P3780 [SDOI2017] Apple Tree

**Tip: In the third partial score, the correct constraint should be $v_i=1$. To respect the original problem, the constraints are not modified.**

Summer is coming, and it is the season of love. The apple tree in front of Little Q’s house is full of bright red round apples. This apple tree is a rooted tree with $n$ nodes, numbered $1$ to $n$. Node $1$ is the root. For every other node, its parent is guaranteed to be a node with a smaller index. Each node has some apples. The $i$-th node has $a_i (a_i > 0)$ apples, and taking one apple from this node gives $v_i (v_i > 0)$ happiness (if you take $k \leq a_i$ apples from this node, you gain $kv_i$ happiness). If you take at least one apple from a node, then you must also take at least one apple from its parent. You are given a positive integer $k$. Pick some apples from the tree. If in total you pick $t$ apples, and among all nodes from which at least one apple is picked, the maximum depth is $h$ (the root has depth $1$), then you must satisfy $t-h \leq k$. Find the maximum total happiness you can obtain.

There are multiple testcases. The first line contains an integer $Q$, the number of testcases. For each testcase, the first line contains two integers $n$ and $k$. Then $n$ lines follow, each describing one node. On the $i$-th line, the first integer is the index of the parent of node $i$ (if $i = 1$, its parent is $0$), the second integer is $a_i$, and the third integer is $v_i$.

Output $Q$ lines, one per testcase. For each testcase, output a single integer, the maximum total happiness that can be obtained.

- For $10\%$ of the testdata, $nk \leq 3000000$ and the height of the tree is $2$. - For $20\%$ of the testdata, $nk \leq 25000000$ and the height of the tree is $2$. - For $20\%$ of the testdata, $nk \leq 25000000$ and all $a_i$ are $1$. - For another $20\%$ of the testdata, $nk \leq 3000000$ with no additional restrictions. - Constraints for $100\%$ of the testdata: $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$. Translated by ChatGPT 5