Bài gợi ý: Không gian phân mảnh
Tóm tắt: Cho một cây gồm \(N\) đỉnh, mỗi đỉnh mang một giá trị nguyên. Ta cần xử lý \(Q\) thao tác gồm thay đổi giá trị tại một đỉnh và tìm đoạn con liên tiếp có tổng lớn nhất trên đường đi giữa hai đỉnh bất kỳ.

Xét đường đi từ đỉnh \(3\) sang đỉnh \(4\) qua đỉnh \(2\). Dãy giá trị tương ứng của các đỉnh trên đường đi này là \(3, -2, 4\). Đoạn con liên tiếp cho tổng lớn nhất là lấy cả dãy với tổng \(3 + (-2) + 4 = 5\). Nếu một đường đi chỉ toàn số âm, đáp số yêu cầu trả về \(0\).

Nếu mỗi lần truy vấn ta lại dùng duyệt theo chiều sâu (DFS) để tìm đường đi và tính tổng đoạn con, chương trình sẽ mất khoảng \(O(N)\) cho mỗi câu hỏi. Với \(N, Q \le 10^5\), tổng số thao tác có thể lên tới \(10^{10}\), gây quá thời gian cho phép.

Ta đang gặp lại bài toán tìm đoạn con có tổng lớn nhất quen thuộc trên mảng một chiều. Để gộp nhanh hai nửa \(L\) và \(R\) của một đoạn, mỗi nút cần lưu bốn thông tin: tổng cả đoạn \(sum\), tiền tố lớn nhất \(pref\), hậu tố lớn nhất \(suff\), và đoạn con lớn nhất \(max\_sub\). Khi nối \(L\) sang trái \(R\), ta có công thức:
\(max\_sub = \max(\{L.max\_sub, R.max\_sub, L.suff + R.pref\})\).
Công thức này xét ba khả năng: đoạn tốt nhất nằm trọn ở nửa trái, nằm trọn ở nửa phải, hoặc băng qua điểm nối giữa hai nửa.

Làm sao mang cấu trúc này lên cây khi đường đi qua nhiều nhánh khác nhau? Ta dùng kỹ thuật phân tách cây thành chuỗi nặng - nhẹ (Heavy-Light Decomposition, hay HLD). Kỹ thuật này trải toàn bộ cây thành các đoạn xích thẳng liên tiếp trên mảng, giúp ta quản lý toàn bộ cây bằng một cây phân đoạn (Segment Tree).

Khi xử lý truy vấn giữa \(u\) và \(v\), ta nhảy từng đoạn xích từ \(u\) và \(v\) lên tổ tiên chung gần nhất. Mỗi bước nhảy trên chuỗi nặng, ta truy vấn trên Segment Tree để lấy kết quả của đoạn đó. Vì đường đi có hướng từ \(u\) lên rồi từ đỉnh chung đi xuống \(v\), ta gom riêng hai nửa đường đi rồi gộp lại ở bước cuối cùng.

Checklist cài đặt:

• Dùng một hàm DFS để tính kích thước cây con và tìm cạnh nặng cho mỗi nút.
• Đánh số lại các đỉnh theo thứ tự đi qua các chuỗi nặng để dựng Segment Tree.
• Viết hàm merge(L, R) để gộp hai đoạn thông tin theo đúng thứ tự trái sang phải.
• Khi truy vấn từ \(u\) và \(v\), gom kết quả nhánh bên \(u\) và nhánh bên \(v\), đảo ngược thông tin nhánh \(u\) trước khi merge với nhánh \(v\), rồi lấy \(\max(ans.max\_sub, 0)\).

Bài tập tương tự:

• CSES - Subarray Sum Queries | Truy vấn tổng đoạn con: Luyện tập thao tác lưu và gộp 4 giá trị của đoạn con lớn nhất trên mảng một chiều.
• Đoạn con có tổng lớn nhất: Làm quen với Segment Tree xử lý truy vấn đoạn con lớn nhất không cập nhật trước khi nâng cấp lên cây.

Bạn hãy bắt đầu bằng việc viết hàm update(1, 1, n, pos[u], x) để thay đổi giá trị của đỉnh trên Segment Tree, sau đó hoàn thiện vòng lặp nhảy chuỗi while (head[u] != head[v]) cho truy vấn đường đi.