Tô Màu Đen Trắng Trên Cây

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved