← 返回题目列表

Codeforces · 1707/D

D. 部分虚拟树

中文机器翻译题面 查看原题

川城似鸟是一位热爱竞技节目的女孩。有一天,她发现了一棵由 $$$n$$$ 个顶点组成的有根树。根是顶点$$$1$$$。作为一个高级问题解决者,她很快就想到了一个问题。

Kawashiro Nitori 有一个顶点集 $$$U=\{1,2,\ldots,n\}$$$。她要和树和布景玩一个游戏。在每次操作中,她都会选择一个顶点集$$$T$$$,其中$$$T$$$是$$$U$$$的部分虚拟树,并将$$$U$$$更改为$$$T$$$。

顶点集 $$$S_1$$$ 是顶点集 $$$S_2$$$ 的部分虚拟树,如果 $$$S_1$$$ 是 $$$S_2$$$ 的子集,$$$S_1 \neq S_2$$$,并且对于 $$$i$$$ 和 $$$j$$$ 中的所有顶点对$$$S_1$$$, $$$\operatorname{LCA}(i,j)$$$ 位于 $$$S_1$$$ 中,其中 $$$\operatorname{LCA}(x,y)$$$ 表示树上顶点 $$$x$$$ 和 $$$y$$$ 的最低公共祖先。请注意,一个顶点集可以有许多不同的部分虚拟树。

Kawashiro Nitori想知道对于每一个可能的$$$k$$$,如果她精确地执行$$$k$$$次操作,她最终可以通过多少种方式得到$$$U=\{1\}$$$?如果存在整数 $$$z$$$ ($$$1 \le z \le k$$$) 使得在 $$$z$$$ 操作之后集合 $$$U$$$ 不同,则两种方式被认为是不同的。

由于答案可能非常大,因此您需要对 $$$p$$$ 求模。保证 $$$p$$$ 是素数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$2 \le n \le 2000$$$, $$$10^8 + 7 \le p \le 10^9+9$$$)。保证 $$$p$$$ 是素数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示 $$$u_i$$$ 和 $$$v_i$$$ 之间的一条边。

保证给定的边形成一棵树。

输出

唯一一行包含 $$$n-1$$$ 整数 - 答案以 $$$p$$$ 为模,$$$k=1,2,\ldots,n-1$$$。

示例

输入 #1

4 998244353
1 2
2 3
1 4

输出 #1

1 6 6

输入 #2

7 100000007
1 2
1 3
2 4
2 5
3 6
3 7

输出 #2

1 47 340 854 880 320

输入 #3

8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8

输出 #3

1 126 1806 8400 16800 15120 5040

注意

在第一个测试用例中,当 $$$k=1$$$ 时,唯一可能的方法是:

1. $$$\{1,2,3,4\} \到 \{1\}$$$。

当$$$k=2$$$时,有$$$6$$$可能的方式:

1. $$$\{1,2,3,4\} \到 \{1,2\} \到 \{1\}$$$;
2. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1\}$$$;
3. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1\}$$$;
4. $$$\{1,2,3,4\} \到 \{1,3\} \到 \{1\}$$$;
5. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1\}$$$;
6. $$$\{1,2,3,4\} \到 \{1,4\} \到 \{1\}$$$。

当$$$k=3$$$时,有$$$6$$$可能的方式:

1. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1,2\} \到 \{1\}$$$;
2. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1,3\} \到 \{1\}$$$;
3. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1,2\} \到 \{1\}$$$;
4. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1,4\} \到 \{1\}$$$;
5. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1,3\} \到 \{1\}$$$;
6. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1,4\} \到 \{1\}$$$。