Hướng dẫn giải của Sinh Vật Huyền Bí

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

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 \cdot a \cdot (K - a)$ vào tổng khoảng cách (vì có đúng $a \cdot (K - a)$ cặp đỉnh đi qua cạnh này).
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.
Độ 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 \cdot 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

Xây dựng cây từ danh sách cạnh. Chọn đỉnh 1 làm gốc.
DFS từ gốc. Với mỗi đỉnh $u$ , duy trì mảng $d p [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.
Khởi tạo: Khi đỉnh $u$ chưa có cây con nào được gộp:
- $d p [u] [0] = 0$ (không chọn đỉnh nào)
- $d p [u] [1] = 0$ (chỉ chọn đỉnh $u$ , chưa có cạnh nào đóng góp)
- $d p [u] [j] = - \infty$ với $j \geq 2$
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^{'} [j + a] = max (d p^{'} [j + a], d p [u] [j] + d p [v] [a] + w \cdot a \cdot (K - a))$
- Lưu ý: $w \cdot a \cdot (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.
Kết quả: $d p [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 \cdot K^{2})$ — tại mỗi cạnh, ta duyệt tối đa $O (K^{2})$ tổ hợp. Với $N, K \leq 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 \cdot K)$ ).
Bộ nhớ: $O (N \cdot K)$

Bình luận

Không có bình luận tại thời điểm này.