Circus

题目描述:

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

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

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

输入格式:

输入的第 1 行包含 N。

第 2≤i≤N 行每行包含两个整数 ai 和 bi，表示树上连接 ai 和 bi 的一条边。

输出格式:

对于每一个 1≤i≤N，在第i行输出 K=i 的答案模 10⁹+7 的余数。

样例输入:

样例1
5
1 2
2 3
3 4
3 5

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

样例输出:

样例1
1
1
3
24
120

样例2
1
1
1
6
30
180
5040
40320

提示:

测试点性质：

• 测试点 3-4 满足 N≤8。
• 测试点 5-7 满足 N≤16。
• 测试点 8-10 满足 N≤100并且树组成了一个“星形”；至多一个结点的度大于二。
• 测试点 11-15 满足 N≤100。
• 测试点 16-20 没有额外限制。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 OPEN Platinum