Truy vấn cây con (Subtree Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một cây có gốc tại đỉnh 1. Mỗi đỉnh có một giá trị. Hãy xử lý phép gán lại giá trị của một đỉnh và truy vấn tổng giá trị trong toàn bộ cây con của một đỉnh.

Dữ liệu vào

Dòng đầu chứa $n,q$. Dòng hai chứa $n$ giá trị. Tiếp theo là $n-1$ cạnh. Sau đó có $q$ truy vấn: 1 s x để gán giá trị đỉnh $s$ bằng $x$, hoặc 2 s để hỏi.

Kết quả

Với mỗi truy vấn loại 2, in tổng giá trị trong cây con.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$, $1\le v_i,x\le10^9$.

Ví dụ

Input

1 5
840
1 1 671
2 1
2 1
1 1 331
2 1

Output

671
671
331

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.