TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

41.3% (52/126)

Tags

Description

帶回了全部的黃金木材,甦蹦開始建造籬笆了。
因為甦蹦迫不期待想栽種傳說中的橘子,建設工程不到一天就竣工了。
甦蹦開心地種下一枚傳說中的橘子的種子,先試驗栽種。

但是隔天早上他發現,他的橘子園被周遭的村人破壞殆盡,種子也被挖走了。
所謂甦蹦可以為了朋友兩肋插刀,但為了橘子可以插朋友兩刀。甦蹦感到又惱又怒,
他決定加蓋一個防護系統,以確保傳說中的橘子能夠安全生長。

他的橘子園中目前有N株橘子幼苗,每株幼苗旁邊都有一台保護電腦。
兩台電腦之間可能會經由線路直接連接、也可能經由其他電腦中繼而間接連接。
甦蹦保證他的防衛系統中,任兩台保護電腦都有恰好一條直接或間接的連接。

每台電腦都有一個保衛值Ki,表示它可以保衛距離它不超過Ki的所有幼苗(包括自己)。
兩株幼苗的距離定義為它們之間會經過幾條線路。

甦蹦想知道這個防衛系統的效率,請你告訴他每台電腦可以保衛幾株幼苗。

Input Format

輸入第一行有一個數字N(N ≤ 100,000),表示有幾株傳說中的橘子的幼苗。
接著一行有N個數字,第i個數字Ki表示第i台電腦的保衛值(電腦編號1~N)。
接著有N-1行,每行有兩個數字Aj, Bj。表示編號Aj和Bj的電腦有直接線路連接。

Output Format

輸出包含N行,第i行的數字Ci表示編號i的電腦可以保衛幾株幼苗。

Sample Input

5
2 1 2 0 2
1 2
1 3
2 5
2 4

Sample Output

5
4
3
1
4

Hints

1可以保衛1, 2, 3, 4, 5
2可以保衛1, 2, 4, 5
3可以保衛1, 2, 3
4可以保衛4
5可以保衛1, 2, 4, 5

Problem Source

原TIOJ1696 / ABCLS Contest, Problem F

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144