分数: 1900 点
问题陈述
有一天,青木向高桥提出了以下问题:
- 你有一棵树 N 顶点和整数 K。顶点已编号 1 通过 N。边由整数对表示 (a_i, b_i).
- 一套 S 树中的顶点,让 f(S) 是给定树的子树中包含所有顶点的最小顶点数 S.
- 有
选择方式 K 树的顶点。对于他们每个人,让 S 是所选顶点的集合,并求出 f(S) 总的来说
方式。 - 由于答案可能非常大,因此将其模数打印出来 924844033(质数)。
由于这对他来说太容易了,他决定为所有人解决这个问题 K = 1,2,...,N.
约束
- 2 ≦ N ≦ 200,000
- 1 ≦ a_i, b_i ≦ 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

上图说明了以下情况: K=2。所选顶点为粉红色,顶点数最少的子树由红线包围。
示例输入 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