Score : $500$ points

问题描述

你得到一棵有 $N$ 个顶点的树。这些顶点按从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

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

• 树的顶点存在 $(2^N-1)$ 个非空子集 $V$。求满足由 $V$ 引出的子图恰好有 $x$ 个连通分量的 $V$ 的数量，并对结果取模 $998244353$。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Solve the following problem for each $x=1,2,\ldots,N$:

• There are $(2^N-1)$ non-empty subsets $V$ of the tree's vertices. Find the number, modulo $998244353$, of such $V$ that the subgraph induced by $V$ has exactly $x$ connected components.

What is an induced subgraph? Let $S$ be the subset of the vertices of a graph $G$; then the subgraph of $G$ induced by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all edges of $G$ whose both ends are contained in $S$.

Constraints

• $1 \leq N \leq 5000$
• $1 \leq a_i \lt b_i \leq N$
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$

$a_1$ $b_1$

$\vdots$

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

Output

Print $N$ lines.
The $i$-th line should contain the answer for $x=i$.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10
5
0
0

The induced subgraph will have two connected components in the following five cases and one in the others.

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

Sample Input 2

2
1 2

Sample Output 2

3
0

Sample Input 3

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

Sample Output 3

140
281
352
195
52
3
0
0
0
0

update @ 2024/3/10 12:00:34