#AT22. Subtree
Subtree
[V] Subtree(dp_v)
来源: AtCoder Educational DP Contest - Problem V 原题时限:2 秒 / 内存:1024 MB
题目描述
有一棵 个顶点的树,顶点编号为 。对于每个 (),第 条边连接顶点 与 。
太郎要把每个顶点染成白色或黑色,要求所有黑色顶点构成的点集连通(即任意两个黑点之间都可以只经过黑点相互到达)。
给定正整数 。对于每个 (),回答:
- 在顶点 必须为黑色的前提下,共有多少种合法染色方案?答案对 取模。
输入格式
输入由标准输入按以下格式给出:
N M
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
输出格式
输出 行。第 行为顶点 必须为黑时的合法染色方案数对 取模的结果。
数据范围
- 输入中的所有值均为整数。
- 给出的图是一棵树。
样例 1
输入:
3 100
1 2
2 3
输出:
3
4
3
样例 2
输入:
4 100
1 2
1 3
1 4
输出:
8
5
5
5
样例 3
输入:
1 100
输出:
1
样例 4
输入:
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
输出:
0
0
1
1
1
0
1
0
1
1