AT_arc087_d.[ARC087F] Squirrel Migration

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$ 。第 $i$ 条边连接顶点 $x_i$ 和 $y_i$ （ $1 \leq i \leq N-1$ ）。对于顶点 $v$ 和 $w$ （ $1 \leq v, w \leq N$ ）， $v$ 和 $w$ 之间的距离 $d(v, w)$ 定义为“从 $v$ 到 $w$ 的路径上包含的边的数目”。

每个顶点上住着一只松鼠。松鼠们决定搬家，搬家的方案如下：首先任选一个 $1$ 到 $N$ 的排列 $p = (p_1, p_2, \dots, p_N)$ 。然后，对于每个 $1 \leq i \leq N$ ，原本住在顶点 $i$ 的松鼠要搬到顶点 $p_i$ 。

松鼠们喜欢移动，因此想让所有松鼠的移动距离之和最大。即，选择排列 $p$ ，使 $d(1,p_1) + d(2,p_2) + \cdots + d(N,p_N)$ 最大。求能够达到这个最大总距离的排列 $p$ 的方案数，结果对 $10^9+7$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\cdots$
$x_{N-1}$ $y_{N-1}$

输出格式

输出满足条件的排列 $p$ 的方案数，对 $10^9+7$ 取模。

输入输出样例

输入#1
```
3
1 2
2 3
```
输出#1
```
3
```
输入#2
```
4
1 2
1 3
1 4
```
输出#2
```
11
```
输入#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
```

说明/提示

限制

$2 \leq N \leq 5,000$
$1 \leq x_i, y_i \leq N$
输入的图保证是一棵树。

样例解释 1

所有松鼠的移动距离之和的最大值是 $4$ 。满足条件的排列 $p$ 有以下 $3$ 种：

$ (2, 3, 1) $
$ (3, 1, 2) $
$ (3, 2, 1) $

样例解释 2

所有松鼠的移动距离之和的最大值是 $6$ 。例如 $p = (2, 1, 4, 3)$ 满足条件。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页