829 . 樹上前綴和
TopCoder
Description
給你一棵 $N$ 個節點的有根樹，根是節點 $1$，每個節點 $i$ 都有一個權重 $w_i$，請對於 $1 \leq i \leq N$ 求出從根到 $i$ 的路徑上，所有的節點權重總和。
Input Format
輸入第一行包含一個整數 $N$，表示樹的大小。
第二行有 $N$ 個整數 $w_1,w_2,\dots,w_N$，表示節點的權重。
接下來有 $N-1$ 行，其中第 $i$ 行有兩個整數 $u_i,v_i$，表示樹上的一條邊連接的兩端點。
- $1 \leq N \leq 5 \times 10^ 5$
- $1 \leq w_i \leq 10^ 9$
- $1 \leq u_i, v_i \leq N$
- 保證輸入是一棵樹
Output Format
輸出 $N$ 行，其中第 $i$ 行包含一個整數，表示從根節點到節點 $i$ 的路徑上，所有節點的權重總和。
Sample Input 1
7
7 7 7 7 7 14 49
1 2
2 4
2 5
4 6
4 7
1 3
7 7 7 7 7 14 49
1 2
2 4
2 5
4 6
4 7
1 3
Sample Output 1
7
14
14
21
21
35
70
14
14
21
21
35
70
Sample Input 2
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 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
Sample Output 2
4
29
21
17
14
36
32
11
38
24
29
21
17
14
36
32
11
38
24
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~22 | 無額外限制 | 100 |