分数: 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
该输入中的图表如下:

对于 k=1,我们可以通过两种方式在顶点上写入数字,如下所示:
- 写作 1, 2, 3 在顶点上 1, 2, 3分别
- 写作 1, 3, 2 在顶点上 1, 2, 3分别
示例输入 2
2 1 2
示例输出 2
1 1
该输入中的图表如下:

示例输入 3
5 1 2 2 3 3 4 3 5
示例输出 3
2 8 12 3 3
该输入中的图表如下:

示例输入 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
该输入中的图表如下:
