P9663 [ICPC 2021 Macao R] Permutation on Tree

给定一个有 $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](https://chatgpt.com/)。

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$.