Sinh Vật Huyền Bí

Hướng tiếp cận

Bài toán yêu cầu chọn đúng $K$ đỉnh trên cây có trọng số cạnh để tối đa hóa tổng khoảng cách giữa tất cả các cặp đỉnh được chọn. Ta sử dụng kỹ thuật DP trên cây kết hợp bài toán ba lô (knapsack on tree).

Nhận xét quan trọng

1. Phân rã theo cạnh: Tổng khoảng cách giữa tất cả các cặp đỉnh được chọn có thể được phân rã theo từng cạnh. Với mỗi cạnh $(u,v)$ có trọng số $w$, nếu ta chọn $a$ đỉnh ở phía cây con chứa $v$ và $K-a$ đỉnh ở phía còn lại, thì cạnh này đóng góp $w·a·(K-a)$ vào tổng khoảng cách (vì có đúng $a·(K-a)$ cặp đỉnh đi qua cạnh này).

2. Bài toán ba lô trên cây: Khi gộp các cây con, ta cần quyết định phân bổ bao nhiêu đỉnh được chọn vào mỗi cây con — đây chính là bài toán ba lô (knapsack) trên cây.

3. Độ phức tạp tối ưu: Nếu gộp cây con một cách cẩn thận (theo kích thước cây con đã xử lý), tổng thời gian là $O(N·K^2)$ trong trường hợp xấu nhất, nhưng trên thực tế nhanh hơn nhờ ràng buộc kích thước cây con.

Thuật toán

1. Xây dựng cây từ danh sách cạnh. Chọn đỉnh 1 làm gốc.

2. DFS từ gốc. Với mỗi đỉnh $u$, duy trì mảng $dp[u][j]$ = tổng đóng góp tối đa từ các cạnh trong cây con gốc $u$, khi chọn đúng $j$ đỉnh trong cây con này.

3. Khởi tạo: Khi đỉnh $u$ chưa có cây con nào được gộp:

   • $dp[u][0]=0$ (không chọn đỉnh nào)
   • $dp[u][1]=0$ (chỉ chọn đỉnh $u$, chưa có cạnh nào đóng góp)
   • $dp[u][j]=-\infty$ với $j\ge 2$

4. Gộp cây con $v$ (với cạnh trọng số $w$) vào $u$:

   • Duyệt tất cả các tổ hợp: $j$ đỉnh đã chọn từ phần đã xử lý của $u$, và $a$ đỉnh chọn từ cây con $v$.
   • Giá trị mới: $d{p}^{\prime }[j+a]=max(d{p}^{\prime }[j+a],dp[u][j]+dp[v][a]+w·a·(K-a))$
   • Lưu ý: $w·a·(K-a)$ là đóng góp của cạnh $(u,v)$ — có $a$ đỉnh bên cây con $v$ và $K-a$ đỉnh bên ngoài.

5. Kết quả: $dp[1][K]$ — giá trị tối đa khi chọn đúng $K$ đỉnh trên toàn bộ cây.

Độ phức tạp

• Thời gian: $O(N·K^2)$ — tại mỗi cạnh, ta duyệt tối đa $O(K^2)$ tổ hợp. Với $N,K\le 2000$, số phép tính tối đa khoảng $8\times {10}^9$ trong trường hợp xấu nhất, nhưng trên thực tế nhanh hơn nhiều nhờ ràng buộc kích thước cây con (tổng tích kích thước khi gộp bị giới hạn bởi $O(N·K)$).
• Bộ nhớ: $O(N·K)$