← 返回题目列表

AtCoder · abc160_f

F. 分配整数

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

分数: 600 点

问题陈述

我们有一棵树 N 顶点编号 1 to N。的 i此树中的第一条边连接顶点 a_i 和 b_i。 对于每个 k=1, ..., N,解决以下问题:

  • 考虑按以下方式在树中的每个顶点上写入一个数字:
    • 首先,写 顶点上的 1 在顶点上 k.
    • 然后,对于每个数字 2, ..., N 按此顺序,在所选顶点上写入数字,如下所示:
      • 选择一个尚未写入数字且与已写入数字的顶点相邻的顶点。如果有多个这样的顶点,则随机选择其中一个。
  • 求出在顶点上写数字的方式的数量,取模 (10^9+7).

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq a_i,b_i \leq N
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
:
a_{N-1} b_{N-1}

输出

对于每个 k=1, 2, ..., N 按照此顺序,打印包含问题答案的行。


示例输入 1

3
1 2
1 3

示例输出 1

2
1
1

该输入中的图表如下:

Figure

对于 k=1,我们可以通过两种方式在顶点上写入数字,如下所示:

  • 写作 1, 2, 3 在顶点上 1, 2, 3分别
  • 写作 1, 3, 2 在顶点上 1, 2, 3分别

示例输入 2

2
1 2

示例输出 2

1
1

该输入中的图表如下:

Figure


示例输入 3

5
1 2
2 3
3 4
3 5

示例输出 3

2
8
12
3
3

该输入中的图表如下:

Figure


示例输入 4

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

示例输出 4

40
280
840
120
120
504
72
72

该输入中的图表如下:

Figure