#AT16. Independent Set
Independent Set
[P] Independent Set(dp_p)
来源: AtCoder Educational DP Contest - Problem P 原题时限:2 秒 / 内存:1024 MB
题目描述
有一棵 个顶点的树,顶点编号为 。对于每个 (),第 条边连接顶点 与 。
太郎决定把每个顶点染成白色或黑色,要求相邻的两个顶点不能同时为黑色。
求所有合法的染色方案数,对 取模。
输入格式
输入由标准输入按以下格式给出:
N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
输出格式
输出合法染色方案数对 取模的结果。
数据范围
- 输入中的所有值均为整数。
- 给出的图是一棵树。
样例 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