Bài gợi ý: Tree Robber

Tóm tắt: Cho một cây \(N\) đỉnh có trọng số \(a_i\). Bạn cần xử lý \(Q\) truy vấn gồm cập nhật trọng số một đỉnh và tìm tổng trọng số lớn nhất của một tập đỉnh không kề nhau trên đường đi đơn giữa hai đỉnh \(u, v\).

Xét ví dụ từ đề bài với đường đi giữa đỉnh \(3\) và \(5\) qua các đỉnh \(3 \to 2 \to 4 \to 5\). Dãy giá trị tương ứng là \(5, 1, 2, 4\). Để không chọn hai đỉnh kề nhau, ta có thể chọn đỉnh \(3\) và đỉnh \(5\), thu được tổng là \(5 + 4 = 9\). Đây là bài toán quen thuộc: chọn các phần tử không liền kề trên một dãy để tổng đạt lớn nhất.

Nếu gọi \(dp[0]\) là tổng lớn nhất khi không chọn đỉnh hiện tại và \(dp[1]\) là khi có chọn đỉnh đó, ta có công thức chuyển:
\(dp_{mới}[0] = \max(dp_{cũ}[0], dp_{cũ}[1])\)
\(dp_{mới}[1] = dp_{cũ}[0] + a_x\)

Với \(Q \le 2 \times 10^5\), nếu mỗi truy vấn đều duyệt lại đường đi từ \(u\) đến \(v\) để tính DP thì sẽ mất quá nhiều thời gian. Ta cần cách gộp nhanh kết quả của nhiều đỉnh liên tiếp mà không phải duyệt từng đỉnh một.

Quan sát thấy phép chuyển DP trên có thể biểu diễn qua phép nhân ma trận với phép cộng thay bằng lấy \(\max\):
\(C_{i, j} = \max_k (A_{i, k} + B_{k, j})\)
Mỗi đỉnh \(x\) tương ứng một ma trận kích thước \(2 \times 2\) là \(M_x = \begin{bmatrix} 0 & a_x \\ 0 & -\infty \end{bmatrix}\). Phép nhân này có tính kết hợp, giúp ta gộp đoạn đường đi thành tích các ma trận.

Để xử lý đường đi trên cây, ta dùng kỹ thuật phân rã chuỗi nặng nhẹ (HLD) kết hợp cây phân đoạn (Segment Tree). Kỹ thuật HLD chia cây thành các đoạn thẳng trên mảng, còn cây phân đoạn quản lý tích ma trận của từng đoạn. Khi cập nhật 1 x y, ta chỉ cần gán lại ma trận tại vị trí của đỉnh \(x\) trên Segment Tree bằng hàm update(pos, M).

Các bước chính khi cài đặt:

• Dùng duyệt cây theo chiều sâu (DFS - thuật toán đi sâu xuống các nhánh của cây trước khi quay lui) để tính kích thước cây con và tạo chuỗi nặng HLD.
• Dựng cây phân đoạn lưu tích ma trận \(2 \times 2\) cho từng nút.
• Khi truy vấn 2 u v, tách đường đi thành hai phần: từ \(u\) lên tổ tiên chung gần nhất và từ tổ tiên chung xuống \(v\).
• Nhân dồn các ma trận theo đúng thứ tự từ \(u\) đến \(v\), bắt đầu từ vector \([0, -\infty]\).

Cuối cùng, lấy \(\max\) giữa \(dp[0]\), \(dp[1]\) và \(0\) để in ra đáp án cho mỗi truy vấn loại 2.