{"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 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$.\n\nDefine 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.\n\n## Input\n\nThere is only one test case in each test file.\n\nThe 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.\n\nFor 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.\n\n## Output\n\nFor 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\n[samples]\n\n## Note\n\nFor 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$.\n\nFor the second sample test case, there is only one good permutation: $\\{1, 2, 3\\}$. It's score is $2$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9663","tags":["动态规划 DP","2021","O2优化","树形 DP","ICPC","澳门"],"sample_group":[["4 2\n1 2\n2 3\n1 4","15"],["3 1\n1 2\n2 3","2"]],"created_at":"2026-03-03 11:09:25"}}