Truy vấn đường đi từ gốc (Path Queries)

Nguồn: CSES

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

Đề bài

Cho 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 trên đường đi từ gốc đến 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 trên đường từ gốc 1 đến đỉnh được hỏi.

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 9
544
2 1
2 1
1 1 324
1 1 888
2 1
1 1 672
2 1
1 1 6
2 1

Output

544
544
888
672
6

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.