题目描述

Given a tree with $n$ vertices where vertex $r$ is the root, we say a permutation $p_1, p_2, \cdots, p_n$ of $n$ is good if it satisfies the following constraint:

• Let $a_x$ be the index of $x$ in the permutation (That is, $p_{a_x} = x$). For all $1 \le u, v \le n$, if vertex $u$ is an ancestor of vertex $v$ in the tree, then $a_u < a_v$.

Define the score of a permutation to be $\sum\limits_{i=1}^{n-1} |p_i - p_{i+1}|$ where $|x|$ is the absolute value of $x$. Calculate the sum of scores of all different good permutations.

输入格式

There is only one test case in each test file.

The first line contains two integers $n$ and $r$ ($2 \le n \le 200$, $1 \le r \le n$) indicating the size of the tree and the root.

For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertex $u_i$ and $v_i$ in the tree.

输出格式

For each test case output one line containing one integer indicating the sum of scores of all different good permutations. As the answer may be large, output the answer modulo $(10^9 + 7)$.

题目大意

【题目描述】

给定一个有 $n$ 个顶点的树，其中顶点 $r$ 是根，如果一个排列 $p_1, p_2, \cdots, p_n$ 满足以下约束条件，我们称其为好排列：

• 设 $a_x$ 是排列中 $x$ 的索引（即 $p_{a_x} = x$）。对于所有 $1 \le u, v \le n$，如果顶点 $u$ 是树中顶点 $v$ 的祖先，则 $a_u < a_v$。

定义排列的分数为 $\sum\limits_{i=1}^{n-1} |p_i - p_{i+1}|$，其中 $|x|$ 表示 $x$ 的绝对值。计算所有不同好排列的分数之和。

【输入格式】

每个测试文件中包含一个测试用例。输入的第一行包含两个整数 $n$ 和 $r$ ($2 \le n \le 200$, $1 \le r \le n$)，表示树的大小和根。

接下来的 $(n - 1)$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树中连接顶点 $u_i$ 和 $v_i$ 的边。

【输出格式】

对于每个测试用例，输出一行，包含一个整数，表示所有不同好排列的分数之和。由于答案可能很大，输出答案对 $(10^9 + 7)$ 取模的结果。

【样例解释】

对于第一个样例测试用例，有三个好排列：$\{2, 1, 3, 4\}$、$\{2, 1, 4, 3\}$ 和 $\{2, 3, 1, 4\}$。它们的分数分别为 $4$、$5$ 和 $6$，因此答案为 $4 + 5 + 6 = 15$。

对于第二个样例测试用例，只有一个好排列：$\{1, 2, 3\}$。它的分数为 $2$。

翻译来自于：ChatGPT。

4 2
1 2
2 3
1 4

15

3 1
1 2
2 3

2

提示

For the first sample test case, there are three good permutations: $\{2, 1, 3, 4\}$, $\{2, 1, 4, 3\}$ and $\{2, 3, 1, 4\}$. Their scores are $4$, $5$ and $6$ respectively so the answer is $4 + 5 + 6 = 15$.

For the second sample test case, there is only one good permutation: $\{1, 2, 3\}$. It's score is $2$.