P1552 [APIO2012] Dispatch

In a ninja gang, some ninjas are selected to be dispatched to customers and are paid according to their work.

In this gang, there is one ninja called the Master. Every ninja except the Master has exactly one superior. For secrecy and to strengthen leadership, all work-related commands are always sent from a superior to their direct subordinate, and cannot be sent in any other way. You are now to recruit a group of ninjas and dispatch them to customers. You must pay a salary for each dispatched ninja, and the total salary must not exceed your budget. In addition, to send commands, you must choose one ninja as the manager, and this manager must be able to send commands to all dispatched ninjas. When sending commands, any ninja (dispatched or not) may act as a relay. The manager themself may or may not be dispatched. If the manager is not dispatched, you do not need to pay the manager’s salary. Your goal is to maximize customer satisfaction within the budget. Customer satisfaction is defined as the number of dispatched ninjas multiplied by the manager’s leadership level, where each ninja has a fixed leadership level. Write a program that, given each ninja $i$’s superior $B_i$, salary $C_i$, leadership level $L_i$, and the total budget $M$, outputs the maximum possible customer satisfaction under the above requirements.

The first line contains two integers $N$ and $M$, where $N$ is the number of ninjas and $M$ is the total salary budget. The next $N$ lines describe each ninja’s superior, salary, and leadership level. The $i$-th line contains three integers $B_i, C_i, L_i$, denoting ninja $i$’s superior, salary, and leadership level, respectively. The Master has $B_i = 0$, and every ninja’s superior index is strictly less than their own, i.e., $B_i \lt i$.

Output a single integer, the maximum customer satisfaction within the budget.

$1 \le N \le 10^5$，$1 \le M \le 10^9$，$0 \le B_i \lt i$，$1 \le C_i \le M$，$1 \le L_i \le 10^9$。 For $30\%$ of the testdata, $N \le 3000$. Translated by ChatGPT 5