Components

题目描述

给出一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。 对于每个 $x=1,2,\ldots,N$ 求解以下问题：

共有 $(2^N-1)$ 个非空顶点子集 $V$。求这样的 $V$ 的数量（对 $998244353$ 取模），使得由 $V$ 所诱导的子图恰好有 $x$ 个连通分量。

输入格式

输入从标准输入给出，格式如下： $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

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$ 给定的图是一棵树。在下面的五种情况下，诱导子图有两个连通分量，其他情况下为一个连通分量。

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

标签: AtCoder|abc287F

来源

AtCoder|abc287F