TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

100.0% (21/21)

Submission's AC Ratio

37.3% (60/161)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (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
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10