Sinh Vật Huyền Bí
Giáo sư Rubeus Hagrid 
đang nghiên cứu về sự đa dạng di truyền của các sinh vật huyền bí trong Rừng Cấm. Ông đã xây dựng một cây phả hệ di truyền gồm sinh vật, trong đó mỗi cạnh nối hai sinh vật có một trọng số biểu thị khoảng cách di truyền giữa chúng.
Hagrid muốn chọn ra đúng sinh vật để thành lập một đàn nuôi mới. Để đảm bảo sự đa dạng di truyền tối đa, ông muốn tổng khoảng cách di truyền giữa tất cả các cặp sinh vật được chọn là lớn nhất có thể.
Khoảng cách di truyền giữa hai sinh vật được tính bằng tổng trọng số các cạnh trên đường đi duy nhất giữa chúng trên cây phả hệ.
Hãy giúp Hagrid tìm tổng khoảng cách lớn nhất có thể.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và — số sinh vật và số sinh vật cần chọn.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên , , — mô tả một cạnh nối sinh vật và với trọng số .
Dữ liệu ra
In ra một số nguyên duy nhất — tổng khoảng cách di truyền lớn nhất giữa tất cả các cặp sinh vật được chọn.
Ràng buộc
- ,
- Các cạnh tạo thành một cây (đồ thị liên thông không có chu trình)
- Kết quả có thể vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 1 2 3 2 3 2 3 4 5 4 5 1 |
22 | Cây là đường thẳng 1-2-3-4-5 với trọng số 3, 2, 5, 1. Chọn 3 sinh vật {1, 3, 5}: d(1,3) = 3+2 = 5, d(1,5) = 3+2+5+1 = 11, d(3,5) = 5+1 = 6. Tổng = 5 + 11 + 6 = 22. |
| 5 3 1 2 4 1 3 7 1 4 2 1 5 6 |
34 | Cây hình sao tâm 1. Chọn {2, 3, 5}: d(2,3) = 4+7 = 11, d(2,5) = 4+6 = 10, d(3,5) = 7+6 = 13. Tổng = 11 + 10 + 13 = 34. |
Ghi chú
Trong ví dụ 1, cũng có thể chọn {1, 4, 5} cho cùng tổng 22: d(1,4) = 10, d(1,5) = 11, d(4,5) = 1. Tổng = 10 + 11 + 1 = 22.
Trong ví dụ 2, các sinh vật 3 và 5 có khoảng cách di truyền lớn nhất (7+6=13), và sinh vật 2 cũng cách xa cả hai, nên chọn bộ ba {2, 3, 5} cho tổng lớn nhất.
Bình luận