TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

21.1% (4/19)

Tags

Description

終於,妁艷和妹妹達成了和諧。

完事之後,兩人躺在地上,妁艷輕拂著妹妹的臉頰,妹妹也一臉幸福的樣子。

「也不知道這是誰為我安排的,不明車輛的驚愕、妹妹的簡訊、形為怪異的學妹們、傲嬌的蘿莉、(請填入接下來發生的事),還有--楓音。」講到這妁艷開始哽咽。

「葛格,你不是還有我嗎?」妹妹安慰妁艷,「只要能讓葛格開心起來,要妹妹幫葛格做什麼都可以!」講到妹妹臉變得紅通通的。

聽到這句話讓妁艷心中產生了一些想法:「不管是快樂的事、悲傷的事、舒服的事,只要是有關那些外星人的事都已經結束了。我要和我所愛的人展開新的生活。」

妁艷好像有一些話想對妹妹說,正當他要說出口時,突然校園開始崩塌。

「可能是他們要消滅留在這裡的證據!」妁艷冷靜的推斷「我不會讓妳受傷的!」看起來妁艷好像想到了解決方法。

妁艷決定要開大絕,其實他之前招降蘿莉時就把她身上的分身道具沒收了。一瞬間,妁艷召喚出許多分身,他們要用那獨一無二的武器把校舍復原。畢竟,如果校舍完全崩毀的話可能會造成不可估計的死亡人數。

學園的地下室總共有n個房間,且有n條通道連接這些房間,保證每兩個房間至少都有一條簡單路相連而且每條通道的長度都是1。

妁艷們要在這n個房間放魔法,但是每個房間需要的魔力不同,讓妁艷不知道哪個房間要派多少妁艷,他只知道每個房間i都有一個脆弱值k_i,代表房間i所需的妁艷數為從房間i走k_i步以內可以到達的房間數。

如果在一個房間多派一個妁艷那這個房間將會因為魔力太強而爆炸,如果在一個房間少派一個妁艷那這個房間將會因為魔力太弱而倒塌。

妁艷能拯救妹妹以及所有學妹們嗎?

Input Format

第一行有正整數n,代表地下室有n個房間和n個走道。
第2行到第n+1行每行有兩個數字a,b,代表有一條走道連接房間a,b。
第n+2行到第2n+1行,第n+1+i行有一個數字k_i,代表房間i得脆弱值。
3<=n<=100000
1<=a,b<=n
0<=k_i<=21474836247
保證地下室任何的簡單環狀走廊的長度不超過20,不低於3

Output Format

總共n行,第i行輸出第i個房間需要幾個妁艷。

Sample Input

7
1 2
2 3
3 1
1 4
4 5
2 6
3 7
1
2
3
1
3
0
3

Sample Output

4
6
7
3
5
1
6

Hints

保護了整個學園的學生之後,妁艷和妹妹打算回家,繼續快樂的兄妹生活。

走到一半,妁艷想到自己還有話沒說,他把手搭在妹妹的肩上,「妹妹,我有話跟你說。」

還沒等到妁艷說出口,妹妹的臉色大變,流露出驚恐與害怕。「你想幹嘛?……不要啊!哥哥你快逃!」妹妹似乎是看到了什麼人。

但妁艷還來不及反應,他就已經失去了知覺,只是他依稀聽到一首他沒聽過的曲子,不斷重複著。

Problem Source

原TIOJ1775 / problem setter:fenzhang

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536