题目描述

高橋君はある日青木君から以下の様な問題を貰いました。

• $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$ で割ったあまりを出力する。

题目大意

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

3
1 2
2 3

3
7
3

4
1 2
1 3
1 4

4
15
13
4

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

7
67
150
179
122
45
7

提示

制約

• $2\ ≦\ N\ ≦\ 200,000$
• $1\ ≦\ a_i,\ b_i\ ≦\ N$
• 与えられるグラフは木である

Sample Explanation 1

 上図は、$K=2$ の場合を図示している。ピンク色の頂点が選んだ頂点で、赤く囲われたのが頂点数最小の部分木である。