F - Components Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点の木があります。頂点には 1 から N までの番号が付いており、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

x=1,2,\ldots,N に対して次の問題を解いてください。

  • 木の頂点の部分集合 V であって空でないものは 2^N-1 通り存在するが、そのうち V による誘導部分グラフの連結成分数が x であるようなものは何通りあるかを 998244353 で割った余りを求めよ。
誘導部分グラフとは S をグラフ G の頂点の部分集合とします。このとき、G の S による誘導部分グラフとは、頂点集合が S で、辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです。

制約

  • 1 \leq N \leq 5000
  • 1 \leq a_i \lt b_i \leq N
  • 与えられるグラフは木

入力

入力は以下の形式で標準入力から与えられる。

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

出力

N 行出力せよ。
i 行目には x=i に対する出力をせよ。

入力例 1

4
1 2
2 3
3 4

出力例 1

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

2
1 2

出力例 2

3
0

入力例 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

Score : 500 points

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