TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

25.0% (5/20)

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 1

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

Sample Output 1

4
6
7
3
5
1
6

Hints

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

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

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

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

Problem Source

原TIOJ1775 / problem setter:fenzhang

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5