Bài gợi ý: Tìm tập độc lập cực đại trên cây — TMAXSET
Tóm tắt: Cho một cây có trọng số tại mỗi đỉnh và nhiều truy vấn. Mỗi truy vấn đưa ra một tập đỉnh con \(Q\), yêu cầu chọn các đỉnh thuộc \(Q\) sao cho không có hai đỉnh nào nối trực tiếp với nhau trên cây và tổng trọng số đạt lớn nhất.

Xét ví dụ với \(3\) đỉnh \(0, 1, 2\) có trọng số lần lượt là \(5, 4, 10\) cùng hai cạnh nối \((0, 2)\) và \((2, 1)\). Với truy vấn \(Q = \{1, 2\}\), hai đỉnh này kề nhau nên ta chỉ được chọn nhiều nhất một đỉnh. Lựa chọn tối ưu là lấy đỉnh \(2\) để đạt tổng trọng số là \(10\).

Thử mọi cách chọn đỉnh trong \(Q\) sẽ mất nhiều thời gian khi số đỉnh lên tới \(200\). Tuy nhiên, cấu trúc cây cho phép ta chia bài toán lớn thành các bài toán nhỏ hơn trên từng nhánh cây con. Ở mỗi đỉnh \(u\), ta chỉ cần quyết định chọn đỉnh \(u\) vào tập hay bỏ qua đỉnh \(u\).

Để giải quyết bài toán, ta dùng phương pháp quy hoạch động trên cây (DP trên cây), tức là lưu lại kết quả tối ưu tại từng cây con để dùng lại. Khi áp dụng duyệt theo chiều sâu (DFS — cách đi dọc theo từng nhánh con xuống đáy rồi mới quay lui), ta duy trì hai giá trị: \(dp[u][1]\) là tổng lớn nhất trong cây con gốc \(u\) khi đỉnh \(u\) được chọn, và \(dp[u][0]\) là tổng lớn nhất khi đỉnh \(u\) không được chọn.

Nếu chọn đỉnh \(u\), mọi nút con \(v\) nối với \(u\) đều không được chọn, nên ta cộng thêm \(dp[v][0]\). Nếu không chọn đỉnh \(u\), nút con \(v\) có thể chọn hoặc không, ta cộng thêm \(\max(dp[v][0], dp[v][1])\). Khi cài đặt, với mỗi truy vấn, ta đánh dấu các đỉnh trong \(Q\) bằng mảng in_Q, gọi dfs(root) để tính bảng phương án, rồi in ra \(\max(dp[root][0], dp[root][1])\).