Tom và Jerry
Đề bài
Mô tả
Tom và Jerry đang rượt đuổi nhau trong một mê cung có dạng cây gồm đỉnh.
Jerry đang ở đỉnh và tại đây có một quả bom do Tom đặt. Quả bom có tầm nổ : khi phát nổ, mọi đỉnh có đường đi đến đỉnh gồm không quá đỉnh (tức là không quá cạnh) đều bị thiêu cháy. Nếu Jerry bị cháy, cậu sẽ ngất xỉu và bị Tom bắt.
Dĩ nhiên Jerry muốn thoát khỏi vùng nổ bằng cách chạy dọc theo các cạnh của mê cung. Ngược lại, Tom muốn bắt Jerry nên định chặn một vài cạnh của mê cung để Jerry không thể đi qua các cạnh đó.
Yêu cầu: Cho truy vấn, mỗi truy vấn gồm hai số và : đỉnh mà Jerry và quả bom đang ở, và tầm nổ của quả bom. Với mỗi truy vấn, hãy giúp Tom tìm số cạnh ít nhất cần chặn để bắt được Jerry, tức là để Jerry không thể chạy tới bất kỳ đỉnh nào nằm ngoài vùng bị thiêu cháy.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên , : số đỉnh của mê cung và số truy vấn.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên , (, ) cho biết có một cạnh nối và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên , (, ) mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in ra trên một dòng số cạnh ít nhất mà Tom cần chặn.
Ràng buộc
- .
- , ; các cạnh tạo thành một cây.
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 3 1 2 2 3 2 4 3 5 3 6 4 7 4 1 2 2 2 1 |
1 0 2 |
Truy vấn 1: vùng cháy là các đỉnh ; chặn cạnh là đủ. Truy vấn 2: mọi đỉnh đều cháy, không cần chặn. Truy vấn 3: vùng cháy là ; phải chặn hai cạnh và . |
| 1 2 1 0 1 1 |
0 0 |
Mê cung chỉ có một đỉnh nên Jerry không có chỗ nào để chạy. |
Bình luận