Sỏi trên cây
Đề bài
Mô tả
Cho một cây gồm đỉnh. Bạn cần đặt sỏi lên mọi đỉnh: đỉnh có viên sỏi, trong đó . Dãy được gọi là một cách đặt.
Với một cách đặt cố định, Alice và Bob chơi trò chơi sau với một quân cờ:
- Đầu tiên, Alice chọn một đỉnh xuất phát và đặt quân cờ lên đó. Việc này không tính là một lượt đi.
- Sau đó hai người lần lượt đi, Alice đi trước.
- Gọi là đỉnh đang có quân cờ. Trong một lượt, người chơi thực hiện đúng một trong hai thao tác:
- Lấy: bỏ đi một hoặc nhiều viên sỏi ở đỉnh , quân cờ vẫn ở .
- Nhảy: di chuyển quân cờ sang một đỉnh kề với sao cho quân cờ chưa từng ở (đỉnh xuất phát được tính là đã từng ở), và số sỏi hiện tại ở bằng đúng số sỏi hiện tại ở . Khi nhảy không có viên sỏi nào bị bỏ đi.
- Người chơi không thể đi được nữa thì thua.
Một cách đặt được gọi là tốt nếu Bob thắng dù Alice chọn đỉnh xuất phát nào, giả sử cả hai đều chơi tối ưu.
Yêu cầu: Đếm số cách đặt tốt. Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho .
Dữ liệu vào
- Dòng đầu tiên gồm một số nguyên (): số đỉnh của cây.
- Mỗi dòng trong dòng tiếp theo gồm hai số nguyên và (, ): một cạnh của cây.
- Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.
Dữ liệu ra
In ra một số nguyên duy nhất: số cách đặt tốt, lấy phần dư khi chia cho .
Ràng buộc
- .
- , ; các cạnh tạo thành một cây.
- Mỗi cách đặt gồm các số với .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 2 3 |
2 | Cây là đường đi , hai cách đặt tốt là và . Với : nếu Alice xuất phát ở đỉnh (hoặc ) thì không lấy được (đỉnh rỗng) và không nhảy được (đỉnh có viên), Alice thua ngay. Nếu Alice xuất phát ở đỉnh thì không nhảy được, phải lấy viên sỏi duy nhất; Bob nhảy sang đỉnh (cả hai đỉnh đều có viên); Alice không lấy được và không nhảy về đỉnh được vì quân cờ đã từng ở đó, Alice thua. Cách đặt không tốt: Alice xuất phát ở đỉnh và nhảy ngay sang đỉnh , Bob không đi được và thua. |
| 7 1 2 1 3 1 4 2 5 2 6 3 7 |
8 | Có cách đặt tốt. |
| 8 1 2 1 3 2 4 1 5 2 6 3 7 4 8 |
16 | Có cách đặt tốt. |
Bình luận