题目描述

给定一个包含 $N$ 个顶点的树。这些顶点编号为 $1$ 到 $N$，第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。

对于每个 $x=1,2,\\ldots,N$，解决以下问题：

• 在树的顶点集上有 $(2^N-1)$ 个非空子集 $V$。找出这样的 $V$ 的个数，满足由 $V$ 引发的子图恰好有 $x$ 个连通分量。

什么是引发的子图？假设 $S$ 是图 $G$ 的顶点子集；那么由 $S$ 引发的 $G$ 的子图是一个顶点集为 $S$，边集包含所有两端都在 $S$ 中的 $G$ 的边的图。

约束条件

• $1 \\leq N \\leq 5000$
• $1 \\leq a_i \\lt b_i \\leq N$
• 给定的图是一棵树。

输入

输入以以下格式从标准输入给出：

$N$ $a_1$ $b_1$ $\\vdots$ $a_{N-1}$ $b_{N-1}$

输出

输出 $N$ 行。
第 $i$ 行应包含 $x=i$ 时的答案。

示例输入 1

4
1 2
2 3
3 4

示例输出 1

10
5
0
0

在以下五种情况下，引发的子图将有两个连通分量，在其他情况下将有一个连通分量。

• $V = \\{1,2,4\\}$
• $V = \\{1,3\\}$
• $V = \\{1,3,4\\}$
• $V = \\{1,4\\}$
• $V = \\{2,4\\}$

示例输入 2

2
1 2

示例输出 2

3
0

示例输入 3

10
3 4
3 6
6 9
1 3
2 4
5 6
6 10
1 8
5 7

示例输出 3

140
281
352
195
52
3
0
0
0
0