Distributing Integers

题目描述

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

考虑以如下方式在树的每个顶点上写入数字： 首先，在顶点 $k$ 上写入 $1$。 然后，对于数字 $2, ..., N$（按此顺序），将该数字写在按如下规则选择的顶点上： 选择一个仍未被写入数字且与已被写入数字的顶点相邻的顶点。如果存在多个这样的顶点，则随机选择其中一个。

求可以在顶点上写入这些数字的方式数，对 $(10^9+7)$ 取模。

输入格式

从标准输入给出如下格式的输入： $N$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$

输出格式

对于每个 $k=1, 2, ..., N$（按此顺序），输出一行，包含该问题的答案。

3
1 2
1 3

2
1
1

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

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq a_i,b_i \leq N$ 给定的图是一棵树。该输入中的图如下所示： 对于 $k=1$，有两种在顶点上写入数字的方式，分别如下：

在顶点 $1, 2, 3$ 上分别写入 $1, 2, 3$ 在顶点 $1, 2, 3$ 上分别写入 $1, 3, 2$
该输入中的图如下所示：
该输入中的图如下所示：
该输入中的图如下所示：

标签: AtCoder|abc160F

来源

AtCoder|abc160F