AT_abc287_f [ABC287F] Components

[problemUrl]: https://atcoder.jp/contests/abc287/tasks/abc287_f $ 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 $ に対する出力をせよ。

### 制約 - $ 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\} $