帶回了全部的黃金木材,甦蹦開始建造籬笆了。
因為甦蹦迫不期待想栽種傳說中的橘子,建設工程不到一天就竣工了。
甦蹦開心地種下一枚傳說中的橘子的種子,先試驗栽種。
但是隔天早上他發現,他的橘子園被周遭的村人破壞殆盡,種子也被挖走了。
所謂甦蹦可以為了朋友兩肋插刀,但為了橘子可以插朋友兩刀。甦蹦感到又惱又怒,
他決定加蓋一個防護系統,以確保傳說中的橘子能夠安全生長。
他的橘子園中目前有N株橘子幼苗,每株幼苗旁邊都有一台保護電腦。
兩台電腦之間可能會經由線路直接連接、也可能經由其他電腦中繼而間接連接。
甦蹦保證他的防衛系統中,任兩台保護電腦都有恰好一條直接或間接的連接。
每台電腦都有一個保衛值Ki,表示它可以保衛距離它不超過Ki的所有幼苗(包括自己)。
兩株幼苗的距離定義為它們之間會經過幾條線路。
甦蹦想知道這個防衛系統的效率,請你告訴他每台電腦可以保衛幾株幼苗。
輸入第一行有一個數字N(N ≤ 100,000),表示有幾株傳說中的橘子的幼苗。
接著一行有N個數字,第i個數字Ki表示第i台電腦的保衛值(電腦編號1~N)。
接著有N-1行,每行有兩個數字Aj, Bj。表示編號Aj和Bj的電腦有直接線路連接。
輸出包含N行,第i行的數字Ci表示編號i的電腦可以保衛幾株幼苗。
1可以保衛1, 2, 3, 4, 5
2可以保衛1, 2, 4, 5
3可以保衛1, 2, 3
4可以保衛4
5可以保衛1, 2, 4, 5
原TIOJ1696 / ABCLS Contest, Problem F
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 |