#AT16. Independent Set

Independent Set

[P] Independent Set(dp_p)

来源: AtCoder Educational DP Contest - Problem P 原题时限:2 秒 / 内存:1024 MB

题目描述

有一棵 NN 个顶点的树,顶点编号为 1,2,…,N1, 2, \ldots, N。对于每个 ii(1≤i≤N−11 \le i \le N-1),第 ii 条边连接顶点 xix_i 与 yiy_i。

太郎决定把每个顶点染成白色或黑色,要求相邻的两个顶点不能同时为黑色。

求所有合法的染色方案数,对 109+710^9 + 7 取模。

输入格式

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}

输出格式

输出合法染色方案数对 109+710^9 + 7 取模的结果。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤1051 \le N \le 10^5
  • 1≤xi,yi≤N1 \le x_i, y_i \le N
  • 给出的图是一棵树。

样例 1

输入:

3
1 2
2 3

输出:

5

样例 2

输入:

4
1 2
1 3
1 4

输出:

9

样例 3

输入:

1

输出:

2

样例 4

输入:

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

输出:

157