Phân tách cây Heavy-Light Decomposition (HLD) cập nhật điểm và tính tổng đường đi

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

• Hiểu kỹ thuật phân tách cây thành các chuỗi xích nặng (Heavy Chains) và cạnh nhẹ (Light Edges).
• Đánh số lại các nút cây theo thứ tự duyệt DFS ưu tiên cạnh nặng để mỗi chuỗi xích tạo thành một đoạn liên tiếp trên Segment Tree.
• Trả lời truy vấn tổng đường đi giữa u và v trong thời gian O(log² N) và cập nhật giá trị nút trong O(log N).

Mô tả bài toán

Cho một cây gồm N đỉnh được đánh số từ 1 đến N với gốc là đỉnh 1. Ban đầu, mỗi đỉnh i có một giá trị số nguyên V_i. Cần xử lý Q truy vấn thuộc 2 loại:

• 1 u x: Cập nhật giá trị tại đỉnh u thành x (V_u = x).
• 2 u v: Tính tổng giá trị của tất cả các đỉnh trên đường đi đơn từ đỉnh u đến đỉnh v.

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⁵.
• 0 ≤ V_i, x ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.