Cho cây \(n\) đỉnh, gốc \(1\), giá trị ban đầu của đỉnh \(i\) là \(a_i\). Xử lý \(m\) thao tác:

• 1 x val: cộng \(val\) vào đỉnh \(x\), trừ \(val\) ở các con của \(x\), cộng \(val\) ở các cháu, rồi tiếp tục đổi dấu qua mỗi cạnh đi xuống. Chỉ cây con của \(x\) bị đổi.
• 2 x: in giá trị hiện tại của đỉnh \(x\).

Dữ liệu vào

• Dòng đầu chứa \(n,m\); dòng tiếp theo chứa \(a_1,\ldots,a_n\).
• \(n-1\) dòng tiếp theo chứa hai đầu của từng cạnh.
• \(m\) dòng cuối chứa các thao tác theo định dạng trên.

Dữ liệu ra

Với mỗi thao tác loại \(2\), in đáp án trên một dòng theo thứ tự nhập.

Ràng buộc

• \(1\le n,m\le200\,000\).
• \(1\le a_i,val\le1000\).
• Mọi số hiệu đỉnh thuộc \([1,n]\); các cạnh tạo thành một cây.

Ví dụ

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

3
3
0

Nguồn

Codeforces 383C - Giá trị lan trên cây.