Cùng cấp độ
Đề bài
Mô tả
Một bang hội trong trò chơi nhập vai có nhân vật, được đánh số từ đến . Nhân vật thứ hiện đang ở cấp độ .
Có liên kết trực tiếp giữa các nhân vật, mỗi liên kết nối hai nhân vật, sao cho giữa hai nhân vật bất kỳ có đúng một đường đi (các nhân vật và các liên kết tạo thành một cây).
Hai nhân vật được liên kết trực tiếp với nhau có thể cùng hoàn thành một nhiệm vụ đôi. Mỗi nhiệm vụ đôi tăng cấp độ của cả hai nhân vật tham gia lên đúng . Cấp độ của một nhân vật không bao giờ giảm, và nhiệm vụ đôi chỉ được thực hiện giữa hai nhân vật được liên kết trực tiếp.
Trưởng bang hội muốn tất cả các nhân vật trong bang hội đạt cùng một cấp độ.
Yêu cầu: Hãy xác định số nhiệm vụ đôi ít nhất cần thực hiện, hoặc cho biết điều đó là không thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa số nguyên .
- Dòng thứ hai chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và thể hiện một liên kết giữa nhân vật và nhân vật .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng số nhiệm vụ đôi ít nhất cần thực hiện, hoặc nếu không thể làm cho tất cả các nhân vật trong bang hội đạt cùng một cấp độ.
Ràng buộc
- .
- ; tổng của tất cả các bộ dữ liệu không vượt quá .
- .
- , ; các liên kết tạo thành một cây.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 1 0 1 1 2 2 3 2 3 5 1 2 4 0 3 3 2 1 2 1 3 1 4 4 2 0 1 3 1 2 2 3 3 4 |
2 -1 4 3 |
Bộ 1: nhân vật và làm một nhiệm vụ, nhân vật và làm một nhiệm vụ; cả ba nhân vật đạt cấp . Bộ 2: hai nhân vật luôn lên cấp cùng nhau nên chênh lệch cấp không bao giờ mất đi. Bộ 3: nhân vật làm một nhiệm vụ với nhân vật , một nhiệm vụ với nhân vật và hai nhiệm vụ với nhân vật ; cả bốn nhân vật đạt cấp . Bộ 4: cặp - làm một nhiệm vụ, cặp - làm hai nhiệm vụ; cả bốn nhân vật đạt cấp . |
| 2 6 2 1 0 0 2 1 2 1 3 2 4 1 5 3 6 4 4 0 1 1 1 1 2 1 3 1 4 |
6 -1 |
Ví dụ bổ sung. Bộ 1: cây là đường . Không thể cùng đạt cấp (khi đó cặp - phải làm nhiệm vụ). Ở cấp , các cặp -, -, -, -, - lần lượt làm nhiệm vụ, tổng . Bộ 2: nếu mọi nhân vật đạt cấp thì mỗi nhân vật làm nhiệm vụ với nhân vật , nên , không có nghiệm nguyên. |
Bình luận