← 返回题目列表

AtCoder · dp_p

P. 独立设置

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有一棵树 N 顶点,编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N - 1), i第一条边连接顶点 x_i 和 y_i.

Taro 决定将每个顶点绘制为白色或黑色。 这里,不允许将两个相邻的顶点都涂成黑色。

求顶点可绘制的方式数量,取模 10^9 + 7.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq x_i, y_i \leq N
  • 给定的图是一棵树。

输入

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

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

输出

打印顶点绘制方式的数量,取模 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