#AT22. Subtree

Subtree

[V] Subtree(dp_v)

来源: AtCoder Educational DP Contest - Problem V 原题时限: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。

太郎要把每个顶点染成白色或黑色,要求所有黑色顶点构成的点集连通(即任意两个黑点之间都可以只经过黑点相互到达)。

给定正整数 MM。对于每个 vv(1≤v≤N1 \le v \le N),回答:

  • 在顶点 vv 必须为黑色的前提下,共有多少种合法染色方案?答案对 MM 取模。

输入格式

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

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

输出格式

输出 NN 行。第 vv 行为顶点 vv 必须为黑时的合法染色方案数对 MM 取模的结果。

数据范围

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

样例 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