📘 Câu chuyện

Trên thân cây cổ thụ có n chiếc lá đánh số từ 1 đến n, nối với nhau thành một mạng lưới không chu trình (một cây). Mỗi lá i ẩn chứa một giọt mật có độ ngon ai. Chú sâu nhỏ thích phiêu lưu:

• Loại 1 (1 u v): chú xuất phát tại lá u, bò dọc thân cây đến lá v và liếm trọn mật của mọi lá trên hành trình. Bọn trẻ muốn biết tổng độ ngon mà chú sâu thưởng thức.
• Loại 2 (2 x w): bọn trẻ rót thêm mật vào lá x, thay đổi độ ngon của lá đó thành w.

📥 Input

• Dòng đầu chứa hai số nguyên n và q (1 <= n, q <= 10^5).
• Dòng thứ hai chứa n số nguyên a1, a2, …, an (1 <= ai <= 10^9).
• n - 1 dòng tiếp theo, mỗi dòng ghi hai số u, v (1 <= u, v <= n) — mô tả một cành cây nối hai lá.
• q dòng cuối, mỗi dòng mô tả một truy vấn:
  • 1 u v — truy vấn loại 1.
  • 2 x w — truy vấn loại 2.

📤 Output

Với mỗi truy vấn loại 1, in ra trên một dòng duy nhất tổng độ ngon của các lá trên đường đi duy nhất từ u tới v. Với truy vấn loại 2, không in gì.

🧪 Ví dụ

Input

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

Output

7
15
22
18

📎 Giải thích

• Ban đầu, đường 4 → 5 đi qua lá 4, 2, 5: 4 + 2 + 1 = 7.
• Cập nhật lá 2 thành 10.
• Đường 4 → 5 lúc này: 4 + 10 + 1 = 15.
• Đường 3 → 4: lá 3, 1, 2, 4: 5 + 3 + 10 + 4 = 22.
• Đường 2 → 3: lá 2, 1, 3: 10 + 3 + 5 = 18.

📎 Hint

• Mình đã nói dùng euler tour thuần thì không được nhưng +lca thì không thành vấn đề. Hãy tìm cách triệt tiêu các cành không cần thiết trên euler tour và bù trừ.