Tutorial — Giá Trị Cạnh

Duyệt qua toàn bộ các cạnh trên đường đi đơn giữa hai nút $a$ và $b$ cho mỗi truy vấn sẽ tốn thời gian $O(N)$ trong trường hợp xấu nhất. Để xử lý các truy vấn thay đổi trọng số và tìm giá trị lớn nhất hiệu quả, ta cần biến đổi cấu trúc đường đi trên cây thành các đoạn liên tiếp trên một dãy số một chiều.

Do mỗi nút ngoại trừ gốc có đúng một nút cha duy nhất, ta có thể lưu trọng số của từng cạnh tại nút con tương ứng của nó. Việc phân chia các đỉnh trên cây thành các chuỗi đường đi nặng và nhẹ giúp đảm bảo đường đi giữa hai nút bất kỳ chỉ đi qua tối đa $O(\log N)$ đoạn liên tiếp trên mảng phẳng.

Sử dụng kỹ thuật Phân tách cây Heavy-Light Decomposition (HLD) kết hợp với Cây phân đoạn (Segment Tree). Khi thực hiện thao tác `CHANGE`, ta cập nhật điểm tại vị trí tương ứng của nút con trên Cây phân đoạn, còn với `QUERY`, ta tích lũy giá trị lớn nhất khi nhảy qua các chuỗi nặng trong thời gian $O(\log^2 N)$.