← 返回题目列表

AtCoder · agc005_f

F. 许多简单的问题

中文机器翻译题面 查看原题

分数: 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