Lau cây
Đề bài
Mô tả
Cho một đồ thị cây có đỉnh (cây là một đồ thị liên thông đỉnh, cạnh). Nút lá là đỉnh có đúng một cạnh kề. Ta thực hiện một phép "lau" các cạnh của cây như sau:
- Chọn hai nút lá bất kì của cây và "lau" tất cả các cạnh trên đường đi ngắn nhất giữa hai nút đó. Nếu số cạnh trên đường đi này là thì ta nói phép "lau" này mất chi phí .
- Quá trình được lặp lại như trên với hai lá khác (trong các nút lá chưa được chọn) cho đến khi tất cả các cạnh của cây đều được "lau" ít nhất một lần.
Như vậy mỗi nút lá được chọn nhiều nhất một lần. Chi phí của một phép "lau" cây là tổng chi phí của tất cả các phép "lau".
Có biến thể của cây . Biến thể thứ () là một đồ thị cây có được bằng cách thêm vào cây ban đầu nút lá. Nút lá thêm vào nút của cây ban đầu là thêm một cạnh nối đỉnh với đỉnh .
Yêu cầu: Với cây biến thể (), hãy tính chi phí nhỏ nhất để "lau" cây ; nếu không thể "lau" hết các cạnh của thì in ra . Chú ý các cây biến thể là độc lập nhau.
Dữ liệu vào
- Dòng đầu ghi hai số nguyên (; ) lần lượt là số đỉnh của cây và biến thể của cây .
- dòng tiếp theo mỗi dòng ghi hai số nguyên () thể hiện cạnh nối giữa hai đỉnh .
- Dòng thứ trong dòng tiếp theo, số nguyên đầu tiên () là số nút lá được thêm vào, tiếp theo số nguyên thể hiện có một nút lá được thêm vào đỉnh . Chú ý, có thể có nhiều nút lá mới được thêm vào cùng một đỉnh của đồ thị và .
Các số trên một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra
Ghi ra dòng, mỗi dòng là chi phí nhỏ nhất để "lau" cây biến thể thứ (hoặc nếu không thể).
Ràng buộc
- ; .
- ; cạnh ban đầu tạo thành một cây.
- ; .
Subtasks
Điểm được tính theo từng test.
- Subtask 1 ( số test): , cây có cạnh nối đỉnh với mọi đỉnh (), các lá thêm vào không có lá nào nối với đỉnh .
- Subtask 2 ( số test): , .
- Subtask 3 ( số test): ().
- Subtask 4 ( số test): không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 3 1 2 2 4 4 5 5 6 5 7 3 4 1 4 2 2 4 1 1 |
-1 10 8 |
Biến thể 1: cây có lá ( và lá mới), số lá lẻ nên không thể dùng hết các lá, cạnh nối với lá không được chọn không được "lau". Biến thể 2: thêm lá vào đỉnh và lá vào đỉnh ; chọn cặp lá mất chi phí , cặp mất chi phí , cặp mất chi phí , tổng là nhỏ nhất. Biến thể 3: thêm lá vào đỉnh , đỉnh không còn là lá. |
| 7 3 1 2 2 4 4 5 5 6 5 7 3 4 4 1 1 2 6 3 6 6 2 2 2 7 |
12 11 -1 |
Bình luận