← 返回题目列表

AtCoder · arc087_d

F. 松鼠迁徙

中文机器翻译题面 查看原题

分数: 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