Tổng đường đi trên cây (LCA)

Cho một cây có $n$ đỉnh, gốc là đỉnh $1$. Đỉnh thứ $u$ có trọng số $w_u$. Cho $q$ truy vấn, mỗi truy vấn gồm hai đỉnh $u$ và $v$; với mỗi truy vấn, hãy tính tổng trọng số của tất cả các đỉnh nằm trên đường đi đơn giản từ $u$ đến $v$ trên cây (bao gồm cả hai đầu mút $u$ và $v$).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.
• $q$ dòng cuối, mỗi dòng chứa hai số nguyên $u$ và $v$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là kết quả của một truy vấn theo thứ tự nhập vào.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $-{10}^9\le w_u\le {10}^9$
• $1\le u,v\le n$
• Dữ liệu cho luôn là một cây hợp lệ.

Ví dụ

Ghi chú

Các trọng số có thể âm; kết quả có thể vượt phạm vi $32$-bit.