Công viên dưa hấu
Đề bài
Mô tả
Vì thành phố Graw đang cần hỗ trợ tài chính, họ quyết định rao bán công viên dưa hấu của mình. May mắn thay, ông Schuyler, người duy nhất đủ khả năng mua công viên, sẵn lòng mua nó.
Schuyler được biết công viên có quả dưa hấu với đủ loại kích thước, và giữa hai quả dưa bất kỳ có đúng một con đường nối chúng. Nói cách khác, khi nhìn bản đồ công viên, ta thấy nó có cấu trúc của một cây.
Schuyler hài lòng với cơ sở hạ tầng của công viên. Tuy nhiên, ông thấy ý tưởng "công viên dưa hấu" khá kỳ lạ, nên ông muốn công viên càng gây ấn tượng càng tốt. Ông quyết định thử dẫn bạn bè đi tham quan công viên theo các con đường khác nhau nối hai quả dưa. Một chuyến tham quan được xác định bởi cặp quả dưa : chuyến đi bắt đầu từ quả dưa và kết thúc ở quả dưa , đi theo con đường duy nhất giữa chúng.
Schuyler nhận thấy bạn bè ông ngạc nhiên mỗi khi họ nhìn thấy một quả dưa lớn hơn tất cả những quả đã thấy trước đó (vì vậy quả dưa đầu tiên của chuyến đi luôn khiến họ ngạc nhiên). Với bản thiết kế trong tay, ông đặt cho Tổng thống Keanu của Graw một số câu hỏi để quyết định có mua công viên hay không: ông liệt kê một số cặp quả dưa, là các chuyến tham quan ông muốn dẫn bạn bè đi, và hỏi Keanu: với mỗi cặp, bạn bè của Schuyler sẽ ngạc nhiên bao nhiêu lần?
Nhiệm vụ của bạn là giúp Keanu trả lời các câu hỏi này.
Dữ liệu vào
- Dòng đầu tiên gồm hai số và : số quả dưa trong công viên và số câu hỏi ().
- Dòng thứ hai gồm số là kích thước của các quả dưa ().
- dòng tiếp theo, mỗi dòng gồm hai số và (, ) cho biết có đường đi trực tiếp giữa quả dưa và quả dưa .
- dòng tiếp theo, mỗi dòng gồm hai số và () mô tả chuyến tham quan đã được mã hóa. Chuyến tham quan thật được giải mã như sau:
- ,
- ,
- trong đó là đáp án của câu hỏi ngay trước đó; với câu hỏi đầu tiên, .
Dữ liệu ra
In ra đáp án của mỗi câu hỏi trên một dòng.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 3 2 4 2 1 3 1 1 3 2 3 3 4 5 3 6 5 5 1 0 3 5 1 |
3 2 1 |
Câu 1: , kích thước trên đường đi là , ngạc nhiên ở . Câu 2: , , kích thước , ngạc nhiên ở . Câu 3: , , kích thước , chỉ ngạc nhiên ở quả đầu tiên. (Đề gốc in sai đáp án ví dụ này, đây là đáp án đã sửa.) |
| 5 4 1 3 4 5 1 1 3 4 1 5 3 5 2 1 3 0 3 1 1 3 4 |
3 1 1 2 |
Ví dụ bổ sung. Các chuyến đi là , , , . Chẳng hạn chuyến đi qua các kích thước nên ngạc nhiên lần. |
Bình luận