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$ 取模后的结果。

输入格式

输入格式（文件 circus.in）： 第 $1$ 行包含 $N$。 第 $2\le i\le N$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示树中 $a_i$ 与 $b_i$ 之间的一条边。

输出格式

输出格式（文件 circus.out）： 对于每个 $1\le i\le N,$ 输出的第 $i$ 行应包含当 $K=i$ 时的答案对 $10^9+7$ 取模后的结果。

5
1 2
2 3
3 4
3 5

1
1
3
24
120

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

1
1
1
6
30
180
5040
40320

提示

对于 $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)$ 不等价。

评分（SCORING）： 测试点 3-4 满足 $N\le 8.$ 测试点 5-7 满足 $N\le 16.$ 测试点 8-10 满足 $N\le 100$ 且树形成一个“星形”；至多只有一个顶点的度数大于二。 测试点 11-15 满足 $N\le 100$。 测试点 16-20 没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum