Tổng cây con với gốc thay đổi

Cho một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$, đỉnh $i$ mang giá trị $a_i$. Các cạnh được cho theo thứ tự và chiều bất kỳ.

Khi chọn một đỉnh $r$ làm gốc, cây con của đỉnh $v$ gồm $v$ và mọi đỉnh mà đường đi từ đỉnh đó tới $r$ đi qua $v$. Nói riêng, nếu $r=v$ thì cây con của $v$ là toàn bộ cây.

Hãy xử lý $q$ thao tác thuộc một trong hai loại:

• 1 v x: gán $a_v=x$.
• 2 r v: coi $r$ là gốc, in ra tổng giá trị các đỉnh trong cây con của $v$.

Mỗi thao tác loại $2$ chỉ chọn gốc cho riêng nó, không ảnh hưởng tới các thao tác sau.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ cho biết có cạnh nối đỉnh $u$ và đỉnh $v$.
• $q$ dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng trên.

Dữ liệu ra

Với mỗi thao tác loại $2$, in ra đáp án trên một dòng.

Ràng buộc

• $1\le n\le 5·{10}^4$
• $1\le q\le 5·{10}^4$, có ít nhất một thao tác loại $2$.
• $|a_i|,|x|\le {10}^9$
• $1\le u,v,r\le n$, với các cạnh thì $u\ne v$.

Ví dụ