AT_abc287_f [ABC287F] Components

题目描述

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

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

• 顶点的非空子集 $V$ 一共有 $2^N-1$ 种，其中有多少种 $V$ 使得由 $V$ 诱导出的子图的连通分量数恰好为 $x$？请将答案对 $998244353$ 取模后输出。

诱导子图的定义如下：设 $S$ 是图 $G$ 的一个顶点子集，则 $G$ 的 $S$ 诱导子图是指顶点集为 $S$，边集为“$G$ 中两端都属于 $S$ 的所有边”的图。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 2
2 3
3 4

输出 #1

10
5
0
0

输入输出样例 #2

输入 #2

2
1 2

输出 #2

3
0

输入输出样例 #3

输入 #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

说明/提示

限制条件

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

样例解释 1

在以下 $5$ 种情况下，诱导子图的连通分量数为 $2$，除此之外均为 $1$。

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

由 ChatGPT 4.1 翻译