1429 . [APIO '12] 忍者調度問題
TopCoder
Tags
Description
在某個忍者流派中，有一位宗師。除了宗師之外，每一名忍者會有一位唯一的上司。為了維護保密性和促進領導能力，所有出動的指令皆需由上司傳送給下屬。除此之外，沒有任何其它傳送指令的方法。
你正準備出動一群忍者來完成客戶指派的任務。為了傳遞出動的指令，你必須選擇一名忍者作為這件任務的主持人。你能夠調度主持人可直接或間接傳達指令的每一位忍者，前提是不能超出此任務的預算。出動每位忍者的費用是固定已知的。主持人本身也可以出動。未出動的忍者可以協助傳遞出動指令，且不需付任何費用。
每位忍者有其領導力值。客戶的滿意度為主持人忍者的領導力值乘上出動的忍者總數。你的目標是在任務預算內，儘可能最大化客戶的滿意度。
給定每一位忍者 $ i (1 \leq i \leq N) $ 的上司 $B_i$、 出動費用 $C_i$ 和領導力值 $L_i$， 以及任務總預算 $M$，請寫一個程式輸出預算內可達成的最大客戶滿意度。
Input Format
第一行包含兩個用空格隔開的整數 $N$ 和 $M$，$N$ 為忍者數量，$M$ 為任務預算。
接來下來的 $N$ 行分別是描述 $N$ 位忍者各自的上司、出動費用和領導能力值。第 $i$ 行包含三個用空格分開的整數 $B_i,C_i,L_i$，其中 $B_i$ 代表為忍者 $i$ 的上司，而他/她的出動費用為 $C_i$，$L_i$ 則代表他/她的領導能力值。若 $B_i = 0$ 表示忍者 $i$ 為宗師。$B_i<i $ 永遠成立，即每一位忍者的上司的編號永遠都小於其本身的編號。
忍者數量（$N$）$1 \leq N \leq 10^ 5$
任務預算（$M$）$1 \leq M \leq 10^ 9$
上司（$B_i$）$0 \leq B_i < N$
出動費用（$C_i$），$1 \leq C_i \leq M$
領導能力值（$L_i$），$1 \leq L_i \leq 10^ 9$
$N \leq 3000$ 的測試資料佔分 30%。
Output Format
輸出最大客戶滿意度。
Sample Input 1
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
Sample Output 1
Hints
範例測試資料中，假如我們選擇忍者 1 當主持人並且出動忍者 3 和 4 時，工資總額為 4，未超出預算 4。因為出動 2 個忍者且主持人領導能力值為 3，客戶的滿意度為 6，此為最大客戶滿意度。
Problem Source
APIO 2012
Set by Yihda Yol
建國中學105學年度校內第五次模擬賽pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~9 | 30 |
| 2 | 0~19 | 70 |