公司派對 (AP325 P-8-11)

有一個公司有 \(n\) 個成員，成員以 \(1 \sim n\) 編號，每個人都有一個領導，除了編號 \(1\) 是公司的總裁，他沒有領導。現在要辦一個公司派對，想要邀請一些人來參加，如果邀請了編號 \(i\) 的人來參加，就會有 \(r(i)\) 的歡樂指數，可是，這個公司的任何人都不想跟他的領導一起參加派對，請你幫忙計算要邀請哪些人來參加，才可以讓參加者的歡樂指數的總和最大。

下圖是一個例子，每個圓圈代表一個人，圓圈內的數字是他的歡樂指數，每個人上方與他連線的就是他的領導，你可以看到，總裁的歡樂指數是 \(1\)，也是全公司最低的。我們可以看到此例中有兩個人的歡樂指數是 \(14\) 與 \(11\)，可惜 \(14\) 是 \(11\) 的領導，所以不能同時邀請這兩人參加。這個例子的最大歡樂指數總和是 \(66\)，扣除歡樂指數分別為 \(1, 3, 3, 4, 14\) 那 \(5\) 個人，其餘的人都參加。

輸入格式

第一行是兩個正整數 \(n\) 與 \(r(1)\)，接下來有 \(n-1\) 行，每行兩個正整數，由 \(i = 2\) 到 \(n\)，依序是 \(p(i)\) 與 \(r(i)\)，其中 \(p(i)\) 是編號 \(i\) 的人的領導。同一行的數字以一個空白隔開。

限制

• \(1 \le n \le 10^5\)。
• \(1 \le r(i) \le 1000\)。
• \(1 \le p(i) \le n\)，\(p(i) \ne i\)；保證領導關係構成一棵以 \(1\) 為根的樹。注意 \(p(i)\) 的編號不一定比 \(i\) 小。

輸出格式

輸出參加派對的最大歡樂指數總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

4 7
1 5
2 6
3 8

範例輸出 1

15

範例輸入 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

範例輸出 2

66

範例說明

範例一：選編號 \(1\) 與 \(4\)，歡樂指數為 \(7 + 8 = 15\)。

範例二：題目敘述中的例子。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 P-8-11，第 300 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。原題出自 NCPC（全國大專電腦軟體設計競賽）。