连通染色 - 代码源竞赛平台

题目描述

蜗蜗得到一棵有 $N$ 个节点的树，节点编号为 $1$ 到 $N$ 。他准备将每个节点染成黑色或白色。

一种染色方案是合法的，当且仅当所有黑色节点构成一个非空连通块。也就是说，任意两个黑色节点之间的简单路径上不能出现白色节点。

对于每个节点 $v$ ，请你分别求出将节点 $v$ 染成黑色的合法方案数量。两个方案只要有一个节点的颜色不同，就视为不同的方案。答案对给定的整数 $M$ 取模。

第一行包含两个整数 $N$ 和 $M$ ，分别表示节点数量和模数。

接下来 $N-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ，表示节点 $x_i$ 与节点 $y_i$ 之间有一条无向边。

输出 $N$ 行，每行一个整数。第 $v$ 行表示节点 $v$ 为黑色时，合法染色方案的数量对 $M$ 取模的结果。

2 6
1 2

2
2

当节点 $1$ 必须为黑色时，可以只将节点 $1$ 染成黑色，也可以将两个节点都染成黑色，共有 $2$ 种合法方案。

当节点 $2$ 必须为黑色时，同样有 $2$ 种合法方案。

对于 100% 的数据，保证 $1\le N\le 10^5$ ， $2\le M\le 10^9$ ， $1\le x_i,y_i\le N$ 。

输入的边构成一棵树， $M$ 不一定是质数。