d117:
P_8_11 公司派對 (NCPC)
Content
有一個公司有 $n$ 個成員，成員以 $1 \sim n$ 編號，每個人都有一個領導，除了編號 $1$ 是公司的總裁，他沒有領導。現在要辦一個公司派對，想要邀請一些人來參加，如果邀請了編號i的人來參加，就會有 $r(i)$ 的歡樂指數，可是，這個公司的任何人都不想跟他的領導一起參加派對，請你幫忙計算要邀請那些人來參加，才可以讓參加者的歡樂指數的總和最大。
右圖是一個例子，每個圓圈代表一個人，圓圈內的數字是他的歡樂指數，每個人上方與他連線的就是他的領導，你可以看到，總裁的歡樂指數是 $1$，也全公司最低的。我們可以看到此例中有兩個人的歡樂指數是 $14$ 與 $11$ ，可惜 $14$ 是 $11$ 的領導，所以不能同時邀請這兩人參加。這個例子的最大歡樂指數總和是 $66$ ，扣除歡樂指數分別為 $1,3,3,4,14$ 那 $5$ 個人，其餘的人都參加。
Input
第一行是兩個正整數 $n$ 與 $r(1)$ ，接下來有 $n-1$行，每行兩個正整數，由 $i=2 \sim n$，依序是 $p(i)$ 與 $r(i)$。 $n$ 不超過 $10^5$， $r(i)$ 不超過 $1000$ 的正整數。
Output
輸出參加派對的最大歡樂指數總和。
Sample Input
#1
4 7 1 5 2 6 3 8
Sample Output
#1
15
Sample Input
#2
15 1 1 5 1 3 1 10 2 14 2 4 3 8 4 3 5 2 5 11 6 2 6 6 8 9 8 6 8 7
Sample Output
#2
66
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint ：
範例一說明：選編號 $1$ 與 $4$，歡樂指數為 $7+8=15$。
範例二說明：題目敘述中的例子。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||