TopCoder

User's AC Ratio

100.0% (80/80)

Submission's AC Ratio

44.1% (203/460)

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

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

Sample Output 1

6

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2
1 1000 262144 262144 1 2
2 1000 262144 262144 1 2
3 1000 262144 262144 1 2
4 1000 262144 262144 1 2
5 1000 262144 262144 1 2
6 1000 262144 262144 1 2
7 1000 262144 262144 1 2
8 1000 262144 262144 1 2
9 1000 262144 262144 1 2
10 1000 262144 262144 2
11 1000 262144 262144 2
12 1000 262144 262144 2
13 1000 262144 262144 2
14 1000 262144 262144 2
15 1000 262144 262144 2
16 1000 262144 262144 2
17 1000 262144 262144 2
18 1000 262144 262144 2
19 1000 262144 262144 2