Problem : 241 - Dispatching

Problem Statistics

Solved Member: 22　　Submission: 118　　User Tried: 22

Statement:

在某個忍者流派中，有一位宗師。除了宗師之外，每一名忍者會有一位唯一的上司。為了維護保密性和促進領導能力，所有出動的指令皆需由上司傳送給下屬。除此之外，沒有任何其它傳送指令的方法。

你正準備出動一群忍者來完成客戶指派的任務。為了傳遞出動的指令，你必須選擇一名忍者作為這件任務的主持人。你能夠調度主持人可直接或間接傳達指令的每一位忍者，前提是不能超出此任務的預算。出動每位忍者的費用是固定已知的。主持人本身也可以出動。未出動的忍者可以協助傳遞出動指令，且不需付任何費用。

每位忍者有其領導力值。客戶的滿意度為主持人忍者的領導力值乘上出動的忍者總數。你的目標是在任務預算內，儘可能最大化客戶的滿意度。

Task:

給定每一位忍者i (1 ≤ i ≤ N) 的上司B_i、出動費用C_i 和領導力值L_i，以及任務總預算M，
請寫一個程式輸出預算內可達成的最大客戶滿意度。

Input:Output:

第一行包含兩個用空格隔開的整數 N 和 M，N為忍者數量，M為任務預算。

接來下來的 N 行分別是描述 N 位忍者各自的上司、出動費用和領導能力值。第 i 行包含三個用空格分開的整數B_i、C_i、L_i，其中Bi 代表為忍者i 的上司，而他/她的出動費用為Ci，Li 則代表他/她的領導能力值。若B_i = 0 表示忍者i 為宗師。B_i＜i 永遠成立，即每一位忍者的上司的編號永遠都小於其本身的編號。

可以保證：
忍者數量(N), 1 ≤ N ≤ 100 000
任務預算(M), 1 ≤ M ≤ 1 000 000 000
上司(B_i), 0 ≤ B_i < i
出動費用(C_i), 1 ≤ C_i ≤ M
領導能力值(L_i), 1 ≤ L_i ≤ 1 000 000 000

N ≤ 3 000 的測試資料佔分30%。

輸出最大客戶滿意度。

Sample Input:Sample Output:

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

HINT:

假如我們選擇忍者1 當主持人並且出動忍者3 和4 時，工資總額為4，未超出預算4。因為出動2 個忍者且主持人領導能力值為3，客戶的滿意度為6，此為最大客戶滿意度。

Source:

APIO 2012

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	2000ms	262144kb
1-1	2000ms	262144kb	10
1-2	2000ms	262144kb
1-3	2000ms	262144kb
1-4	2000ms	262144kb
1-5	2000ms	262144kb
1-6	2000ms	262144kb
1-7	2000ms	262144kb
1-8	2000ms	262144kb
1-9	2000ms	262144kb
1-10	2000ms	262144kb
2-1	2000ms	262144kb	10
2-2	2000ms	262144kb
2-3	2000ms	262144kb
2-4	2000ms	262144kb
2-5	2000ms	262144kb
2-6	2000ms	262144kb
2-7	2000ms	262144kb
2-8	2000ms	262144kb
2-9	2000ms	262144kb
2-10	2000ms	262144kb
3-1	2000ms	262144kb	10
3-2	2000ms	262144kb
3-3	2000ms	262144kb
3-4	2000ms	262144kb
3-5	2000ms	262144kb
3-6	2000ms	262144kb
3-7	2000ms	262144kb
3-8	2000ms	262144kb
3-9	2000ms	262144kb
3-10	2000ms	262144kb
4-1	2000ms	262144kb	70
4-2	2000ms	262144kb
4-3	2000ms	262144kb
4-4	2000ms	262144kb
4-5	2000ms	262144kb
4-6	2000ms	262144kb
4-7	2000ms	262144kb
4-8	2000ms	262144kb
4-9	2000ms	262144kb
4-10	2000ms	262144kb