[ICPC 2021 Macao R] Permutation on Tree

Luogu

IDLGP9663

Time1000ms

Memory512MB

DifficultyP6

动态规划 DP2021O2优化树形 DPICPC澳门

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. ## Input 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. ## Output 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)$. [samples] ## Note 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$.

Samples

Input #1

Output #1

Input #2

3 1
1 2
2 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2021 Macao R] Permutation on Tree",
    "description": {
      "content": "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 t",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9663"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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:\n\n- Let $a_x$ be the index of $x$ in t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments