/ 
Time Limit: 5 sec / Memory Limit: 512 MB
配点 : 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) を「パス v-w に含まれる辺の本数」と定義します。
木の各頂点にはリスが 1 匹ずつ住んでいます。 リスたちは次のようにして引っ越しをすることにしました。 まず、(1, 2, ..., N) の順列 p = (p_1, p_2, ..., p_N) を自由にひとつ選びます。 その後、各 1 \leq i \leq N について、頂点 i に住んでいたリスは頂点 p_i へ引っ越します。
リスたちは移動が好きなので、各リスの移動距離の総和が最大になるように引っ越しをすることにしました。 すなわち、d(1, p_1) + d(2, p_2) + ... + d(N, p_N) が最大になるように p を選ぶことにしました。 このような 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 は次の 3 通りです。
- (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
Score : 800 points
Problem Statement
There is a tree with N vertices. The vertices are numbered 1 through N. The i-th edge (1 \leq i \leq N - 1) connects Vertex x_i and y_i. For vertices v and w (1 \leq v, w \leq N), we will define the distance between v and w d(v, w) as "the number of edges contained in the path v-w".
A squirrel lives in each vertex of the tree. They are planning to move, as follows. First, they will freely choose a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Then, for each 1 \leq i \leq N, the squirrel that lived in Vertex i will move to Vertex p_i.
Since they like long travels, they have decided to maximize the total distance they traveled during the process. That is, they will choose p so that d(1, p_1) + d(2, p_2) + ... + d(N, p_N) will be maximized. How many such ways are there to choose p, modulo 10^9 + 7?
Constraints
- 2 \leq N \leq 5,000
- 1 \leq x_i, y_i \leq N
- The input graph is a tree.
Input
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}
Output
Print the number of the ways to choose p so that the condition is satisfied, modulo 10^9 + 7.
Sample Input 1
3 1 2 2 3
Sample Output 1
3
The maximum possible distance traveled by squirrels is 4. There are three choices of p that achieve it, as follows:
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
Sample Input 2
4 1 2 1 3 1 4
Sample Output 2
11
The maximum possible distance traveled by squirrels is 6. For example, p = (2, 1, 4, 3) achieves it.
Sample Input 3
6 1 2 1 3 1 4 2 5 2 6
Sample Output 3
36
Sample Input 4
7 1 2 6 3 4 5 1 7 1 5 2 3
Sample Output 4
396