[HOJ 191][SGU 507]一個大秘寶 (題目備份)

File failed to load: file:///C:/Users/Burney/Desktop/New%20folder/191_files/extensions/MathZoom.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 191 - 一個大秘寶

Problem Statistics

Solved Member: 17　　Submission: 164　　User Tried: 19

Problem：

hh在偉大的航道上發掘哥爾D羅傑的大秘寶。

在上次盜墓的過程，hh找到了一張地圖，意外發現那是One Piece。

One Piece是存放在一個洞窟裡，一個洞窟有n個洞穴，由n-1條路徑連接這n個洞穴，其中有m個走到底的洞穴放著秘寶，對於這m個有祕寶的洞穴，我們稱呼他為OPX，已知祕寶的價值與重量成正比，每個OPX的祕寶價值也不盡相同。

可憐的hh在登島的時候，夥伴全都被大海怪抓到海底，只有hh跟藏寶圖倖存。

因為兩手只能拿兩份秘寶，所以hh希望兩份祕寶的相差重量D越少越好，如此hh才能平衡的走出洞窟。

現在出現一個讓hh很困擾的問題，由於往回走很low，所以hh想知道若現在在洞穴Vi(非OPX)，使用hh神技──觸手奪寶術！一次抓走兩份秘寶，對於往之前來的方向伸出觸手時，何時要轉彎hh不知道，所以只能一路往未探險的方向伸。

因為hh可能在任意點才發現此問題，所以請對於每個非OPX都輸出一個最小D。

為了化簡一下問題，我們定1為洞窟的起點，而只有m-n+1 ~ n是OPX。

Input：

一組測試檔有多筆測試資料。

對於每筆測試資料:
第一行有兩個數字n, m(1 ≤ m < n ≤ 200000)，分別代表洞穴數與OPX
第二行有n-1個數字，分別是2~n洞穴的前一個洞穴 a2~an，保證 ai < i。
第三行有m個數字，分別代表n-m+1 ~ n的OPX上的祕寶重量Ki ( -1000000 ≤ Ki ≤ 1000000 )

Output：

對於每組測試資料輸出n-m個數字於一行，每個數字以空白隔開。
若hh抓不到兩份寶藏，hh會因為不平衡摔倒，請輸出2³¹-1，代表hh哭哭了。

Sample Input：

5 4
1 1 1 1
1 4 7 9

5 4
1 1 1 1
1 4 7 10

7 4
1 2 1 2 3 3
2 10 7 15

2 1
1
100

Sample Output：

2
3
3 3 8
2147483647

Source：

SGU 507

Problem Setter

hanhan0912

Testdata：

Test	Time	Memory	Score
0	1000ms	262144kb
1	2000ms	262144kb	10
2	2000ms	262144kb	10
3	2000ms	262144kb	10
4	2000ms	262144kb	10
5	6000ms	262144kb	10
6	6000ms	262144kb	10
7	6000ms	262144kb	10
8	6000ms	262144kb	10
9	6000ms	262144kb	10
10	6000ms	262144kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。