F - 分配整数

分数：$600$ 分

题目描述

我们有一个顶点编号为 $1$ 到 $N$ 的树。在这棵树上，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 对于每个 $k=1,...,N$，解决以下问题：

• 考虑在树的每个顶点上写一个数，顺序如下：
  • 首先，在顶点 $k$ 上写 $1$。
  • 然后，对于 $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$ 上打印一行，其中包含问题的答案。

3
1 2
1 3

2
1
1

这个样例中的图如下所示：

对于 $k=1$，我们有两种方式在顶点上写数字，如下所示：

• 在顶点 $1, 2, 3$ 上写 $1, 2, 3$
• 在顶点 $1, 2, 3$ 上写 $1, 3, 2$

2
1 2

1
1

这个样例中的图如下所示：

5
1 2
2 3
3 4
3 5

2
8
12
3
3

这个样例中的图如下所示：

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

40
280
840
120
120
504
72
72

这个样例中的图如下所示：