1642 . 光彩炫目的寶石
TopCoder
Tags
Description
在某座杳無人煙的深山中，傳說有著一個神秘的山洞，裡面擺放著許多禁忌的祕寶。從古到今，很多人都想前往一窺究竟，也吸引了許許多多的探險家跟寶物獵人，
但至今只要踏上這趟旅途的人都相當於是走上了一條不歸路──真的是不歸路，從來沒有人再次回來過……
你是一位著名的探險家，想當然爾，你當然在對這個傳說感到不可思議的同時也激起了你對於探險的慾望！
因此，你決定動身前往這個傳說中的神秘山洞。在做好了萬全的準備，包括當地的大略地形探測，以及準備好食糧、指南針等等長期探險活動必需的物品之後，
終於正式出發了！
花了約三天的時間，你終於到了傳說中深山之中，走著走著，開始發生你意料之外的事情……首先，你的指南針失靈了！
這使得你無法辨認方向，森林的樹蔭密不透光，微弱的光源使得整座森林看起來宛如漆黑的牢獄一般令人感到莫大的恐懼……
繼續走下去，你看到了草叢中有具白骨，看來是以前嘗試來探險的人悲劇的下場，不過你並不因此而畏懼，一味地走下去。
終於！你在某個岩石險壁的轉角中看到了理當不應該出現在漆黑森林中的一道光線。沿著危險的立足點慢慢走過去……
一個跳躍，你跳到了感覺上應該是光線來源的平台上，同一時間，你被刺眼的光線照得睜不開眼睛。而當你再次睜開眼睛時，你愣住了。
擺在你眼前的是一排排看起來被刻意放置在岩石上的華麗寶石！仔細數了一數，竟然有 N 個之多！而所謂的光芒更竟是由它們自身發出的！
在欣喜之餘，你不忘保持著警戒──往往看似越好的寶物，越可能有險惡的陷阱守護著它們！
果不其然，當你嘗試地拋擲了一個小石頭到這個寶窟的正中央時，地面上迅速的刺出了一根根的金屬長刺，而他們所匯聚的一點正是剛剛小石頭落地的位置上方。
然而這點危機感並沒有打消你取得寶物的念頭。你巧妙的避過了這個洞穴中所有的陷阱，終於到達了寶石堆的前方。
看到這成群的發光寶石，你突然回想起出發前村莊中一位煉金術師跟你說的話：
「如果你遇到的是自身會發光的 SKYLYIAN DIAMONDS ，那麼千萬要小心！它們之間有著特殊的『同質性』，一不小心將會產生嚴重的後果！」
你從這位煉金術師的口中得知，這種特殊的寶石幾乎都有所對應的高階寶石（有少數的並沒有），
當你同時擁有了兩個或以上數量的寶石且它們都有對應的高階寶石並恰好都是同一種類的話，它們就會產生一種劇變，
這種力量甚至有可能扭曲周遭的空間！因此絕對不可以讓這種事情發生。而因應之道就是同時擁有它們對應的高階寶石，
這麼一來高階寶石就能發揮其力量，鎮壓住劇變的發生。簡單來說，就是當你取走了兩個或以上數量屬於同一種高階寶石的寶石的話，
就必須馬上去取該種高階寶石鎮壓之。在所有的發光寶石中，你注意到有一顆特別閃亮的寶石（同時看起來也是最大顆的），
而以往的經驗給了你一種預感：一旦你從台座上取走了那顆寶石，山洞便會崩塌！
你對山洞中的所有寶石做了一些分析，大致上估計了他們各自的價值，而你手邊有煉金術師交給你的，SKYLYIAN DIAMONDS 的高階寶石對應表。
在你預感的前提下，你想知道你至多可以帶走總價值多少的寶石。
注意：一次動作只能取一顆寶石!!
Input Format
本題有多筆測試資料。對於每一筆測試資料，第一行有一個整數 N；之後第二行有 N 個整數，第 i 個整數 Vi 代表第 i 個寶石的價值；
第三行亦有 N 個整數，第 i 個整數 Hi 則代表第 i 個寶石的高階寶石編號，若該寶石沒有對應的高階寶石，則 Hi 將會是0。
以N = -1作為輸入的結尾（你不應該對這作出任何回答）。
對於所有的測試資料，保證0 < N ≤ 500000 且 1 ≤ Vi ≤ 10000, 0 ≤ Hi ≤ N, ∀ 1 ≤ i ≤ N。
而寶石將被編號成 1 到 N 的正整數，最閃亮且最大顆的寶石必定被編號成 1。（因此 H1 將永遠會是 0）
Output Format
請輸出一個整數 S 代表你最多可以安全地帶走總價值 S 的寶石。
Sample Input 1
7 3 2 4 5 1 1 2 0 1 1 1 2 2 2 5 2 1 1 1 1 0 1 1 1 1 -1
Sample Output 1
14 4
Hints
以下範例解釋：
第一筆範例取編號 1, 2, 4, 5, 6, 7 的寶石, 得到最佳總價值 3 + 2 + 5 + 1 + 1 + 2 = 14 .
第二筆範例取編號 1, 2, 3 的寶石, 得到最佳總價值 2 + 1 + 1 = 4. (不只一組可能的解可以得到最佳值, 如取編號 1, 2, 4 的寶石)
Problem Source
原TIOJ1642 / Skyly & Shik Contest II (Problem C)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |