📘 Mô tả

Cho một cây gồm n đỉnh, đánh số từ 1 đến n. Mỗi đỉnh i có trọng số là wi.

Bạn cần tính tổng trọng số của các đỉnh trong cây con gốc tại mỗi đỉnh u, tức là tổng trọng số của u và tất cả các đỉnh nằm trong cây con có gốc là u.

📥 Input

• Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 10⁵): số đỉnh của cây.
• Dòng thứ hai gồm n số nguyên w1, w2, ..., wn (1 ≤ wi ≤ 10⁴): trọng số của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v (1 ≤ u, v ≤ n): biểu thị một cạnh nối giữa hai đỉnh u và v.

📤 Output

In ra n số nguyên, số thứ i là tổng trọng số của cây con gốc tại đỉnh i.

🧪 Ví dụ

Input:

5
1 2 3 4 5
1 2
1 3
3 4
3 5

Output:

15 2 12 4 5

📎 Ghi chú

• Cây có gốc tại đỉnh 1 bao gồm tất cả các đỉnh, tổng trọng số là 15.
• Cây con gốc tại đỉnh 2 chỉ có chính nó nên tổng là 2.
• Cây con gốc tại đỉnh 3 gồm các đỉnh 3, 4, 5 nên tổng là 3 + 4 + 5 = 12.