Truy vấn đường đi từ gốc

Cho một cây gồm $n$ đỉnh, gốc tại đỉnh 1. Mỗi đỉnh có một giá trị ban đầu. Xử lý $q$ thao tác:

• Loại 1: Cập nhật giá trị của một đỉnh.
• Loại 2: Tính tổng giá trị tất cả các đỉnh trên đường đi từ gốc đến một đỉnh.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$.

Dòng thứ hai chứa $n$ số nguyên là giá trị ban đầu của các đỉnh từ $1$ đến $n$.

• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.

• $q$ dòng tiếp theo, mỗi dòng là một thao tác:

• 1 s x — cập nhật giá trị đỉnh $s$ thành $x$.
• 2 s — tính tổng giá trị trên đường đi từ gốc đến $s$.

Dữ liệu ra

Với mỗi thao tác loại 2, in ra tổng giá trị trên đường đi.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le v_i,x\le {10}^9$
• $1\le a,b,s\le n$

Ví dụ