Tô Màu Đen Trắng Trên Cây
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Bạn cần tô mỗi đỉnh bằng một trong hai màu: đen hoặc trắng sao cho không có hai đỉnh kề nhau nào cùng được tô màu đen. Hãy đếm số cách tô màu hợp lệ, lấy phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
- Một số nguyên duy nhất là số cách tô màu hợp lệ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 1 2 1 3 |
5 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le u, v \le N$
Community Discussion