Quy hoạch động Ba-lô trên cây: Kỹ thuật chặn trên O(N^2)
Cho một cây có gốc tại đỉnh 1 gồm N đỉnh. Mỗi đỉnh u có một giá trị Vu. Bạn cần chọn đúng K đỉnh trên cây sao cho: Nếu một đỉnh u (u ≠ 1) được chọn thì đỉnh cha p(u) của nó cũng…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: tree dp, knapsack dp.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững bài toán Tree Knapsack (chọn k đỉnh trên cây con thỏa mãn tính kết nối hoặc ràng buộc cha con).
- Hiểu kỹ thuật giới hạn kích thước cây con
min(sub_size[u], K): Mặc dù nhìn như 3 vòng lặp O(N3), nhưng thực chất tổng số cặp nút được duyệt đúng bằng số cặp nút có chung LCA ⇒ O(N2) hoặc O(N · K).
Mô tả bài toán
Cho một cây có gốc tại đỉnh 1 gồm N đỉnh. Mỗi đỉnh u có một giá trị Vu. Bạn cần chọn đúng K đỉnh trên cây sao cho: Nếu một đỉnh u (u ≠ 1) được chọn thì đỉnh cha p(u) của nó cũng bắt buộc phải được chọn (đỉnh 1 luôn phải được chọn nếu K ≥ 1). Hãy tìm tổng giá trị lớn nhất của K đỉnh được chọn.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N, K (1 ≤ K ≤ N ≤ 2000).
- Dòng 2: N số nguyên V1, V2, …, VN (-109 ≤ Vi ≤ 109).
- N-1 dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v mô tả một cạnh của cây.
Output
- In ra một số nguyên duy nhất là tổng giá trị lớn nhất.
Ràng buộc
- 1 ≤ K ≤ N ≤ 2000.
- Thời gian: 1000ms. Bộ nhớ: 256MB.
Ví dụ 1
Input
5 3
10 -5 20 15 -10
1 2
1 3
2 4
2 5Output
45
*Giải thích: Chọn các đỉnh {1, 3, 2} tổng 10 + 20 - 5 = 25. Hoặc {1, 2, 4} tổng 10 - 5 + 15 = 20. Nếu chọn {1, 3, ?}, đỉnh 1 (10), đỉnh 3 (20) và đỉnh 2 (giá trị -5) là 25. Nhưng nếu chọn {1, 3} thì đỉnh thứ 3 là ai? Cạnh 1-2 và 1-3. Đỉnh 4 nối với 2. Nếu chọn 4 thì phải chọn 2 và 1 $\implies$ {1, 2, 4} có tổng $10 - 5 + 15 = 20$. Nếu chọn {1, 3, 2} có tổng $10 + 20 - 5 = 25$. Khoan, nếu đỉnh 3 có con không? Không. Cạnh: 1-2, 1-3, 2-4, 2-5. Với K=3, các tập hợp hợp lệ gồm: {1, 2, 3} tổng 25; {1, 2, 4} tổng 20; {1, 2, 5} tổng -5. Max là 25.*Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.