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
Sample Output 1
7 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
Sample Output 2
4 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 |