分数: 800 点
问题陈述
有一棵树 N 顶点。顶点已编号 1 通过 N。的 i第边缘 (1 \leq i \leq N - 1) 连接顶点 x_i 和 y_i.对于顶点 v 和 w (1 \leq v, w \leq N),我们将定义之间的距离 v 和 w d(v, w) as“路径中包含的边数 v-w".
树的每个顶点都生活着一只松鼠。他们计划搬迁如下。首先,他们将自由选择排列 (1, 2, ..., N), p = (p_1, p_2, ..., p_N)。然后,对于每个 1 \leq i \leq N,住在 Vertex 的松鼠 i 将移动到顶点 p_i.
由于他们喜欢长途旅行,因此他们决定最大化在此过程中旅行的总距离。也就是说,他们会选择 p 这样 d(1, p_1) + d(2, p_2) + ... + d(N, p_N) 将最大化。这样的方式有多少种可供选择 p,模数 10^9 + 7?
约束
- 2 \leq N \leq 5,000
- 1 \leq x_i, y_i \leq N
- 输入图是一棵树。
输入
输入由标准输入按以下格式给出:
N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}
输出
打印选择的方式数量 p 使得条件满足,取模 10^9 + 7.
示例输入 1
3 1 2 2 3
示例输出 1
3
松鼠可能行走的最大距离是 4。 有以下三种选择 p 实现它,如下:
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
示例输入 2
4 1 2 1 3 1 4
示例输出 2
11
松鼠可能行走的最大距离是 6。 例如, p = (2, 1, 4, 3) 实现了它。
示例输入 3
6 1 2 1 3 1 4 2 5 2 6
示例输出 3
36
示例输入 4
7 1 2 6 3 4 5 1 7 1 5 2 3
示例输出 4
396