连通分量

题目描述

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

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

树的顶点共有 $2^N - 1$ 个非空子集 $V$。求由 $V$ 导出的子图恰好有 $x$ 个连通分量的 $V$ 的个数,对 $998244353$ 取模。

什么是导出子图? 设 $S$ 为图 $G$ 的顶点集合的一个子集,则 $G$ 中由 $S$ 导出的子图是指:顶点集为 $S$,边集由 $G$ 中所有两端点均在 $S$ 中的边组成的图。

输入格式

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

$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

在以下 5 种情况下,导出子图有 2 个连通分量,其余情况均为 1 个:

$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

数据范围

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