3397. [USACO20 Open Platinum]Circus

【题目描述】

Farmer John 马戏团的 $N$ 头奶牛（$1 \leq N \leq 10^5$）正在准备她们接下来的演出。演出在一棵结点编号为 $1\ldots N$ 的树上进行。演出的“起始状态”可以定义为一个整数 $1 \leq K \leq N$ 以及奶牛 $1\dots K$ 在树上的结点分布，使得没有两头奶牛位于相同的结点。

在一场演出中，奶牛们可以进行任意次数的“移动”。在一次移动中，一头奶牛从她的当前所在结点移动到一个未被占据的相邻结点。称两个起始状态是等价的，如果一个状态可以通过一系列移动到达另一个。

对于每一个 $1 \leq K \leq N$，帮助奶牛们求出起始状态的等价类数量：即可选出的起始状态的最大数量，使得两两不等价。由于这些数字可能很大，输出模 $10^9 + 7$ 的余数。

【输入格式】

输入的第 $1$ 行包含 $N$。

第 $2\le i\le N$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示树上连接 $a_i$ 和 $b_i$ 的一条边。

【输出格式】

对于每一个 $1\le i\le N$，在第 $i$ 行输出 $K=i$ 的答案模 $10^9+7$ 的余数。

【样例输入1】

5
1 2
2 3
3 4
3 5

【样例输出1】

1
1
3
24
120

【样例输入2】

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

【样例输出2】

1
1
1
6
30
180
5040
40320

【样例解释】

样例 1 解释:

对于 $K=1$ 和 $K=2$，任意两个状态之间都可以相互到达。

考虑 $K=3$，令 $c_i$ 为奶牛 $i$ 的位置。状态 $(c_1,c_2,c_3)=(1,2,3)$ 等价于状态 $(1,2,5)$ 和 $(1,3,2)$，然而不等价于状态 $(2,1,3)$。

【提示】

对于$ 20\% $的测试数据(测试点$ 1 \sim 4 $)，满足$ N \le 8 $。

对于$ 35\% $的测试数据(测试点$ 1 \sim 7 $)，满足$ N \le 16 $。

另有$ 15\% $的测试数据(测试点$ 8 \sim 10 $)，树组成了一个“星形”，即至多一个结点的度大于二。

对于$ 75\% $的测试数据(测试点$ 1 \sim 15 $)，满足$ N \le 100 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Platinum 组