AT_dp_p Independent Set
题目描述
有一棵包含 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N-1$），第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。
太郎君打算将每个顶点涂成白色或黑色。但要求相邻的两个顶点不能同时被涂成黑色。
请问有多少种顶点着色的方案？请输出方案数对 $10^9+7$ 取模的结果。
输入格式
输入以如下格式从标准输入读入。
> $N$
> $x_1$ $y_1$
> $x_2$ $y_2$
> $\vdots$
> $x_{N-1}$ $y_{N-1}$
输出格式
输出顶点着色方案数对 $10^9+7$ 取模的结果。
说明/提示
## 限制条件
- 所有输入均为整数。
- $1 \leq N \leq 10^5$
- $1 \leq x_i, y_i \leq N$
- 给定的图是一棵树。
## 样例解释 1
顶点的着色方案如图，共有 $5$ 种。
## 样例解释 2
顶点的着色方案如图，共有 $9$ 种。
由 ChatGPT 4.1 翻译