F - 组件

得分：$500$ 分

问题描述

给定一个有 $N$ 个顶点的树，顶点从 $1$ 到 $N$ 编号，第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。

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

• 树的顶点有 $(2^N - 1)$ 个非空子集 $V$。计算具有恰好 $x$ 个连通分量的子图 $V$ 的数量对 $998244353$ 取模的结果。

约束条件

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

输入

从标准输入中按以下格式输入：

$N$

$a_1$ $b_1$

$\vdots$

$a_{N-1}$ $b_{N-1}$

输出

打印 $N$ 行。
第 $i$ 行应该包含 $x=i$ 的答案。

4
1 2
2 3
3 4

10
5
0
0

以下五种情况下，诱导子图将具有两个连通分量，其他情况下则只有一个连通分量。

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

2
1 2

3
0

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

140
281
352
195
52
3
0
0
0
0