內容
在某個忍者流派中，有一位宗師。除了宗師之外，每一名忍者會有一位唯一的上司。為了維護保密性和促進領導能力，所有出動的指令皆需由上司傳送給下屬。除此之外，沒有任何其它傳送指令的方法。你正準備出動一群忍者來完成客戶指派的任務。為了傳遞出動的指令，你必須選擇一名忍者作為這件任務的主持人。你能夠調度主持人可直接或間接傳達指令的每一位忍者，前提是不能超出此任務的預算。出動每位忍者的費用是固定已知的。主持人本身也可以出動。未出動的忍者可以協助傳遞出動指令，且不需付任何費用。每位忍者有其領導力值。客戶的滿意度為主持人忍者的領導力值乘上出動的忍者總數。你的目標是在任務預算內，儘可能最大化客戶的滿意度。
問題
給定每一位忍者i (1<= i <= N) 的上司Bi、出動費用Ci 和領導力值Li，以及任務總預算M，
請寫一個程式輸出預算內可達成的最大客戶滿意度。
限制
忍者數量(N), 1 <= N <= 100000
任務預算(M), 1 <= M <= 1000000000
上司(Bi), 0 <= Bi < i
出動費用(Ci), 1 <= Ci <=M
領導能力值(Li), 1 <= Li <= 1000000000
輸入說明
第一行包含兩個用空格隔開的整數N 和M，N 為忍者數量，M 為任務預算。
接來下來的N 行分別是描述N 位忍者各自的上司、出動費用和領導能力值。第i 行
包含三個用空格分開的整數Bi、Ci、Li，其中Bi 代表為忍者i 的上司，而他/她的出
動費用為Ci，Li 則代表他/她的領導能力值。若Bi = 0 表示忍者i 為宗師。Bi＜i 永
遠成立，即每一位忍者的上司的編號永遠都小於其本身的編號。
輸出說明
輸出最大客戶滿意度。
範例輸入
#1
5 4 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1
範例輸出
#1
6
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
在上述範例中，假如我們選擇忍者1 當主持人並且出動忍者3 和4 時，工資總額為4，未超出預算4。因為出動2 個忍者且主持人領導能力值為3，客戶的滿意度為6，此為最大客戶滿意度。
標籤:
出處:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||