APIO '12 P1 - Dispatching

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

In a sect of ninja, ninjas are dispatched to a client, and they are rewarded according to their work.

In this sect, there is one ninja called the Master. Every ninja except the Master has one and only one boss.

In order to preserve the confidentiality and to encourage leadership, any instructions concerning their work are always sent by a boss to his/her subordinates. It is forbidden to send instructions by other methods. You are gathering a number of ninjas and dispatch them to a client. You have to pay salaries to dispatched ninjas. For each ninja, the amount of salary for him/her is fixed. The total amount of salaries paid to them should be within a budget. Moreover, in order to send instructions, you have to choose a ninja as a manager who can send instructions to all dispatched ninjas. When instructions are sent, a ninja who is not dispatched may mediate the transmission. The manager may or may not be dispatched. If the manager is not dispatched, he will not be paid.

You would like to maximize the satisfaction level of the client as much as possible within a budget. The satisfaction level of the client is calculated as the product of the total number of dispatched ninjas and the leadership level of the manager. For each ninja, his/her leadership level is fixed.


Write a program that, given the boss B_i, the amount of salary C_i, the leadership level L_i of each ninja i (1 \le i \le N), and the budget for salaries M, outputs the maximum value of the satisfaction level of the client when the manager and dispatched ninjas are chosen so that all the conditions are fulfilled.


1 \le N \le 100\,000 The number of ninjas
1 \le M \le 1\,000\,000\,000 The budget for salaries
0 \le B_i < i The boss of each ninja
1 \le C_i \le M The amount of salary of each ninja
1 \le L_i \le 1\,000\,000\,000 The leadership level of each ninja

Input Specification

Read the following data from the standard input.

  • The first line of input contains two space separated integers N, M, where N is the number of ninjas and M is the budget.
  • The following N lines describe the boss, salary, leadership level of each ninja. The (i + 1)-th line contains three space separated integers B_i, C_i, L_i, describing that the boss of ninja i is ninja B_i, the amount of his/her salary is C_i, and his/her leadership level is L_i. The ninja i is the Master if B_i = 0. Since the inequality B_i < i is always satisfied, for each ninja, the number of his/her boss is always smaller than the number of himself/herself.

Output Specification

Write the maximum value of the satisfaction level of the client to the standard output.


In test cases worth 30\% of the full score, N \le 3\,000.

Sample Input 1

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output 1


If we choose ninja 1 as a manager and ninja 3, 4 as dispatched ninjas, the total amount of salaries is 4 which does not exceed the budget 4. Since the number of dispatched ninjas is 2 and the leadership level of the manager is 3, the satisfaction level of the client is 6. This is the maximum value.


There are no comments at the moment.