TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (25/25)

Submission's AC Ratio

52.1% (76/146)

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

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

Sample Output

6

Hints

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

Problem Source

APIO 2012
Set by Yihda Yol
建國中學105學年度校內第五次模擬賽pB

Subtasks

For Testdata: 0 ~ 9, Score: 30
For Testdata: 0 ~ 19, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144