Atcoder Educational DP Contest P - Independent Set

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho 1 cây có ~N~ đỉnh, được đánh số ~1,2,...,N~. Cây có ~N-1~ cạnh, trong đó cạnh thứ ~i~ nối giữa đỉnh ~x_i~ và ~y_i~.

Taro sẽ tô màu mỗi đỉnh trên cây bằng ~1~ trong ~2~ màu đen hoặc trắng. Ngoài ra, không được phép tồn tại ~2~ đỉnh kề mà cả ~2~ đỉnh đều có màu đen.

Tìm số cách tô các đỉnh thỏa mãn, modulo ~10^9+7~

Input

Dòng đầu tiên gồm số nguyên ~N~ ~(1 \le N \le 10^5)~.

~N-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên. Trong đó dòng thứ ~i~ chứa ~2~ số nguyên ~x_i~ và ~y_i~.

Input đảm bảo đồ thị đã cho là cây.

Output

In ra số cách tô thỏa mãn modulo ~10^9+7~

Sample 1

Input
3
1 2
2 3
Output
5

Có ~5~ cách tô các đỉnh như sau:

Sample 2

Input
4
1 2
1 3
1 4
Output
9

Có ~9~ cách tô các đỉnh như sau:

Sample 3

Input
1
Output
2

Sample 4

Input
10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
Output
157

Comments

Please read the guidelines before commenting.


There are no comments at the moment.