[AGC005F] Many Easy Problems

题意翻译

给定一棵无根树,定义 $f(i)$,对于所有大小为 $i$ 的点集,求出能够包含它的最小连通块大小之和。对于 $i=1 \to n$ 的所有 $i$,求出 $f(i)$。

题目描述

[problemUrl]: https://atcoder.jp/contests/agc005/tasks/agc005_f 高橋君はある日青木君から以下の様な問題を貰いました。 - $ N $ 頂点の木と、整数 $ K $ が与えられる。木の頂点は $ 1,2,...,N $ と番号がついているものとし、辺は $ (a_i,\ b_i) $ で表す。 - 頂点の集合 $ S $ について $ f(S) $ を、$ S $ をすべて含む部分木の頂点数の最小値とする - 木から $ K $ 個の頂点を選ぶ方法は $ _NC_K $ 通りあるが、それぞれについて選んだ頂点を $ S $ とし、 $ f(S) $ の総和を求める - 答えは大きくなることがあるので、$ 924844033 $(素数) で割ったあまりを出力する 高橋君にとってこの問題は簡単すぎました。なので $ K\ =\ 1,2,...,N $ 全てについてこの問題を解くことにしました。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_{N-1} $ $ b_{N-1} $

输出格式


$ N $ 行出力する。$ i $ 行目には、$ K=i $ の時の問題の答えを $ 924844033 $ で割ったあまりを出力する。

输入输出样例

输入样例 #1

3
1 2
2 3

输出样例 #1

3
7
3

输入样例 #2

4
1 2
1 3
1 4

输出样例 #2

4
15
13
4

输入样例 #3

7
1 2
2 3
2 4
4 5
4 6
6 7

输出样例 #3

7
67
150
179
122
45
7

说明

### 制約 - $ 2\ ≦\ N\ ≦\ 200,000 $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N $ - 与えられるグラフは木である ### Sample Explanation 1 !\[\](https://atcoder.jp/img/agc005/44e2fd5d5e0fe66d1d238ee502639e4e.png) 上図は、$ K=2 $ の場合を図示している。ピンク色の頂点が選んだ頂点で、赤く囲われたのが頂点数最小の部分木である。