题目描述

$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$ に含まれるものすべて」であるようなグラフです。

输入格式

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

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

输出格式

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

题目大意

有一棵大小为 $n$ 的树，节点编号 $1\dots n$，从中任意选出一些点，显然有 $2^n-1$ 种方案。每一种选法中选择的点都会形成一些连通块，对于 $x=1\dots n$，求连通块数量恰好是 $x$ 的选法数量，对 $998244353$ 取模。

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$
• 与えられるグラフは木

Sample Explanation 1

以下の $5$ 通りでは誘導部分グラフの連結成分数が $2$、これら以外では $1$ になります。 - $V\ =\ \{1,2,4\}$ - $V\ =\ \{1,3\}$ - $V\ =\ \{1,3,4\}$ - $V\ =\ \{1,4\}$ - $V\ =\ \{2,4\}$