AT_abc160_f [ABC160F] Distributing Integers

题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。这棵树的第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。

对于 $k=1,\ldots,N$，请解决以下问题：

• 按照如下步骤，在树的每个顶点上写一个整数。
  • 首先，在顶点 $k$ 上写 $1$。
  • 然后依次将 $2,\ldots,N$ 写到顶点上。每次选择要写入的顶点时，需满足以下条件：
    • 该顶点尚未被写入整数，且与已写入整数的顶点相邻。如果有多个满足条件的顶点，则从中随机选择一个。
• 求所有可能的整数写法的数量，并对 $10^9+7$ 取模。

输入格式

输入以如下格式从标准输入读入。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出格式

请按顺序输出 $k=1,2,\ldots,N$ 的答案，每行一个。

输入输出样例 #1

输入 #1

3
1 2
1 3

输出 #1

2
1
1

输入输出样例 #2

输入 #2

2
1 2

输出 #2

1
1

输入输出样例 #3

输入 #3

5
1 2
2 3
3 4
3 5

输出 #3

2
8
12
3
3

输入输出样例 #4

输入 #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

说明/提示

限制条件

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

样例解释 1

该输入对应的图如下所示。

对于 $k=1$ 的情况，有如下两种整数写法：

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

样例解释 2

该输入对应的图如下所示。

样例解释 3

该输入对应的图如下所示。

样例解释 4

该输入对应的图如下所示。

由 ChatGPT 4.1 翻译