Cập nhật khoảng cách trên cây cán chổi

Cho một cây có $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$. Cây có tính chất đặc biệt: mọi đỉnh khác đỉnh $1$ đều có bậc không vượt quá $2$. (Nói cách khác, sau khi bỏ đỉnh $1$, cây tách thành một số đường thẳng đính vào đỉnh $1$.)

Khoảng cách giữa hai đỉnh là số cạnh trên đường đi ngắn nhất giữa chúng.

Ban đầu, mỗi đỉnh chứa giá trị $0$. Bạn cần xử lý $q$ truy vấn thuộc một trong hai dạng:

• 0 v x d — cộng thêm $x$ vào giá trị của tất cả các đỉnh cách đỉnh $v$ không quá $d$ cạnh.
• 1 v — in ra giá trị hiện tại đang ghi tại đỉnh $v$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ — mô tả một cạnh của cây.
• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên.

Dữ liệu ra

Với mỗi truy vấn dạng 1 v, in ra giá trị hiện tại tại đỉnh $v$ trên một dòng riêng.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le q\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le v\le n$, $1\le x\le {10}^4$, $1\le d<n$
• Đồ thị đề bài luôn là một cây thỏa mãn tính chất trên.

Ví dụ