ARBORE - Thắc mắc của Mitrut
Xem dạng PDF
Gửi bài giải
Điểm:
3,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Mitrut có số tự nhiên ~N~ và một cây có ~N~ đỉnh. Cậu thắc mắc rằng có bao nhiêu cách để đặt ~N~ số khác nhau vào cây, mỗi số trên một nút thỏa mản rằng số ở nút ~A~ nhỏ hơn số của tất cả các nút là con của ~A~. Gốc của cây luôn là nút ~1~.
Do kết quả có thể rất lớn nên bạn chỉ cần tìm số dư khi chia kết quả tìm được với ~666013~.
Input
- Dòng đầu tiên ghi số ~N\ (1 ≤N ≤ 100000)~;
- ~N-1~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~x~ và ~y~, thể hiện có một cạnh nối giữa hai đỉnh ~x~ và ~y\ (x ≠y,1 ≤ x ≤ N , 1 ≤ y ≤ N)~.
Giới hạn:
- ~70\%~ số test có ~N ≤ 2000~;
- ~10\%~ số test có ~N ≤ 7~.
Output
- Ghi ra một số nguyên duy nhất là kết quả cần tính.
Sample
Input #1
5
1 2
3 1
2 4
2 5
Output #1
8
Hint
Với bộ test trên, các cách để đánh số là:
Problem source: Kc97ble - Free Contest
Bình luận
Gợi í cách làm của tui: