內容
相信大家都有玩過需要點技能樹的遊戲，我們都希望能在有限的技能點情況下點出最大的能力值。
已知技能樹是一棵由$n$個技能構成的有根樹，每個技能都有其能力值$w_i$，要想學習一個技能必須要花費一點技能點數，且要已經學會其父親的技能，不過若想學習的技能為根，則可直接學習(但還是要花費一點技能點數)
你目前具有的技能點數為$k$，試求能獲得的最大值為何。
輸入說明
第1列有一數$n$，代表技能樹是一棵由$n$個技能構成的有根樹
第2列有$n$個數，其中第$i$個數代表其父親為$a_i$
第3列有$n$個數，其中第$i$個數代表其能力值為$w_i$
最後一列有一數$k$，代表目前具有的技能點數
對於100%的測資 $1 \leq n \leq 5000$, $1 \leq w_i \leq 100$, $1 \leq k \leq n$, 保證給的圖為有根樹
輸出說明
請輸出能獲得的最大值
範例輸入
4 -1 1 1 3 3 1 2 10 3
範例輸出
15
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
提示 ：
標籤:
出處:
DDJ Regular ContestRound#8
[管理者：
fdhs108_38002
(NULL)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||