Independent Set

题意翻译

给一棵树,每一个点可以染成黑色或白色,任意两个相邻节点不能都是黑色,求方案数,结果对 $10^9+7$ 取模。

题目描述

[problemUrl]: https://dp.contest.atcoder.jp/tasks/dp_p $ N $ 頂点の木があります。 頂点には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ( $ 1\ \leq\ i\ \leq\ N\ -\ 1 $ ) について、 $ i $ 番目の辺は頂点 $ x_i $ と $ y_i $ を結んでいます。 太郎君は、各頂点を白または黒で塗ることにしました。 ただし、隣り合う頂点どうしをともに黒で塗ってはいけません。 頂点の色の組合せは何通りでしょうか? $ 10^9\ +\ 7 $ で割った余りを求めてください。 There is a tree with $ N $ vertices, numbered $ 1,\ 2,\ \ldots,\ N $ . For each $ i $ ( $ 1\ \leq\ i\ \leq\ N\ -\ 1 $ ), the $ i $ -th edge connects Vertex $ x_i $ and $ y_i $ . Taro has decided to paint each vertex in white or black. Here, it is not allowed to paint two adjacent vertices both in black. Find the number of ways in which the vertices can be painted, modulo $ 10^9\ +\ 7 $ .

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_{N\ -\ 1} $ $ y_{N\ -\ 1} $ ```

输出格式


Print the number of ways in which the vertices can be painted, modulo $ 10^9\ +\ 7 $ .

输入输出样例

输入样例 #1

3
1 2
2 3

输出样例 #1

5

输入样例 #2

4
1 2
1 3
1 4

输出样例 #2

9

输入样例 #3

1

输出样例 #3

2

输入样例 #4

10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

输出样例 #4

157

输入样例 #5

3
1 2
2 3

输出样例 #5

5

输入样例 #6

4
1 2
1 3
1 4

输出样例 #6

9

输入样例 #7

1

输出样例 #7

2

输入样例 #8

10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

输出样例 #8

157

说明

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - 与えられるグラフは木である。 ### Constraints - All values in input are integers. - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - The given graph is a tree. ### Sample Explanation 1 頂点の色の組合せは次図の $ 5 $ 通りです。 !\[\](https://img.atcoder.jp/dp/indep\_0\_muffet.png) ### Sample Explanation 2 頂点の色の組合せは次図の $ 9 $ 通りです。 !\[\](https://img.atcoder.jp/dp/indep\_1\_muffet.png) ### Sample Explanation 5 There are five ways to paint the vertices, as follows: !\[\](https://img.atcoder.jp/dp/indep\_0\_muffet.png) ### Sample Explanation 6 There are nine ways to paint the vertices, as follows: !\[\](https://img.atcoder.jp/dp/indep\_1\_muffet.png)