Kỹ thuật Euler Tour: Cập nhật cây con và Truy vấn đường đi

Mục tiêu kiến thức

• Nắm vững kỹ thuật trải phẳng cây (Tree Flattening / Euler Tour Technique): Gán mỗi đỉnh u một khoảng thời gian [tin_u, tout_u].
• Toàn bộ cây con gốc u trở thành một đoạn con liên tiếp [tin_u, tout_u] trên mảng 1D.
• Thao tác cập nhật cộng giá trị cho toàn bộ cây con gốc u tương đương cập nhật đoạn [tin_u, tout_u] trên Segment Tree trong O(log N).

Mô tả bài toán

Cho một cây có gốc tại đỉnh 1 gồm N đỉnh. Mỗi đỉnh ban đầu có giá trị V_u. Bạn cần xử lý Q truy vấn:

• 1 u x: Cộng thêm x vào tất cả các đỉnh trong cây con gốc u.
• 2 u: In ra giá trị hiện tại tại đỉnh u.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N, Q ≤ 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.