📘 Mô tả

Một cái cây có n đỉnh được đánh số từ 1 đến n, mỗi đỉnh i mang giá trị ban đầu ai gọi là độ ngon. Có q truy vấn được thực hiện trên cây.

Có hai loại truy vấn:

• 1 u v: hỏi tổng độ ngon trên đường đi giữa hai đỉnh u và v trên cây.
• 2 u k: cộng thêm k vào tất cả các đỉnh thuộc cây con gốc tại đỉnh u.

📥 Input

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) — số đỉnh của cây.
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 109).
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả một cạnh nối hai đỉnh.
• Dòng tiếp theo chứa số nguyên q — số lượng truy vấn.
• q dòng cuối, mỗi dòng chứa một trong hai loại truy vấn đã nêu.

📤 Output

Với mỗi truy vấn loại 1, in ra tổng độ ngon trên đường đi từ u tới v.

🧪 Ví dụ

Input:

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

Output:

7
16
11

📎 Ghi chú

• Truy vấn đầu tiên: đường đi từ 4 → 2 → 5: tổng = 4 + 2 + 1 = 7.
• Truy vấn thứ hai: tăng giá trị tất cả các đỉnh trong cây con tại đỉnh 2 lên 1 → đỉnh 2, 4, 5 đều tăng thêm 1.
• Truy vấn tiếp theo: đường đi từ 3 → 1 → 2 → 4: tổng = 5 + 3 + 3 + 4 = 15.
• Truy vấn cuối: đường đi từ 2 → 1 → 3: tổng = 3 + 3 + 4 = 10.