TopCoder

abcabcabc

User's AC Ratio

100.0% (4/4)

100.0% (4/4)

給你一棵 $N$ 個節點的有根樹，根是節點 $1$，每個節點 $i$ 都有一個權重 $w_i$，請對於 $1 \leq i \leq N$ 求出從根到 $i$ 的路徑上，所有的節點權重總和。

輸入第一行包含一個整數 $N$，表示樹的大小。

第二行有 $N$ 個整數 $w_1,w_2,\dots,w_N$，表示節點的權重。

接下來有 $N-1$ 行，其中第 $i$ 行有兩個整數 $u_i,v_i$，表示樹上的一條邊連接的兩端點。

輸出 $N$ 行，其中第 $i$ 行包含一個整數，表示從根節點到節點 $i$ 的路徑上，所有節點的權重總和。

7
7 7 7 7 7 14 49
1 2
2 4
2 5
4 6
4 7
1 3

7
14
14
21
21
35
70

10
4 8 7 6 3 4 8 7 6 3
7 9
5 3
10 7
5 8
7 6
4 8
2 3
8 1
3 10

4
29
21
17
14
36
32
11
38
24

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~22	無額外限制	100

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2
18	1000	524288	65536	2
19	1000	524288	65536	2
20	1000	524288	65536	2
21	1000	524288	65536	2
22	1000	524288	65536	2