Tổng tiền tố trên cây

Cho một cây có $n$ đỉnh, đánh số từ $1$ đến $n$, gốc tại đỉnh $1$. Mỗi đỉnh $u$ có một trọng số $w_u$ (có thể âm). Cây được mô tả bởi $n-1$ cạnh không định hướng.

Bạn cần xử lý $q$ truy vấn. Với mỗi truy vấn cho một đỉnh $u$, hãy tính tổng trọng số của tất cả các đỉnh nằm trên đường đi từ gốc (đỉnh $1$) đến đỉnh $u$, bao gồm cả hai đầu mút.

Dữ liệu vào

• Dòng đầu: số nguyên $n$ — số đỉnh.
• Dòng thứ hai: $n$ số nguyên $w_1,w_2,\dots ,w_n$ — trọng số các đỉnh.
• $n-1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u,v$ ($1\le u,v\le n$, $u\ne v$) — mô tả một cạnh không định hướng của cây.
• Dòng tiếp theo: số nguyên $q$ — số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng gồm một số nguyên $u$ ($1\le u\le n$) — đỉnh cần truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $-{10}^9\le w_u\le {10}^9$
• Đồ thị đã cho được đảm bảo là một cây.

Ví dụ

Ghi chú

Vì kết quả có thể rất lớn, hãy sử dụng kiểu số nguyên 64-bit (long long trong C++).