Bài toán

Cho một cây gốc có ~ n ~ đỉnh. Mỗi đỉnh có một giá trị ban đầu. Nhiệm vụ của bạn là xử lý hai loại truy vấn:

1. Thay đổi giá trị của một đỉnh: Đặt giá trị của đỉnh ~ s ~ thành ~ x ~.
2. Tính tổng giá trị trên đường từ gốc đến đỉnh ~ s ~: Tính tổng giá trị từ gốc (đỉnh 1) đến đỉnh ~ s ~.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số lượng đỉnh và số lượng truy vấn (~ 1 \leq n, q \leq 2 \cdot 10^5 ~).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ v_1, v_2, \ldots, v_n ~: giá trị ban đầu của các đỉnh.
• Tiếp theo là ~ n-1 ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: biểu diễn một cạnh giữa hai đỉnh ~ a ~ và ~ b ~.
• Cuối cùng là ~ q ~ dòng, mỗi dòng là một truy vấn thuộc một trong hai dạng:
  • 1 s x: đặt giá trị của đỉnh ~ s ~ thành ~ x ~.
  • 2 s: tính tổng giá trị từ gốc đến đỉnh ~ s ~.

Đầu ra

• Với mỗi truy vấn dạng 2 s, in ra tổng giá trị từ gốc đến ~ s ~.

Kiểm tra với ví dụ

Input:

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

Output:

11
16

Giải thích:

• Truy vấn 2 3: Tổng giá trị từ gốc đến ~ 3 ~ là ~ 4 + 5 + 2 = 11 ~.
• Truy vấn 1 3 10: Thay đổi giá trị tại ~ 3 ~ thành ~ 10 ~.
• Truy vấn 2 3: Tổng giá trị từ gốc đến ~ 3 ~ là ~ 4 + 10 + 2 = 16 ~.