#P9663. [ICPC2021 Macao R] Permutation on Tree
[ICPC2021 Macao R] Permutation on Tree
题目描述
Given a tree with vertices where vertex is the root, we say a permutation of is good if it satisfies the following constraint:
- Let be the index of in the permutation (That is, ). For all , if vertex is an ancestor of vertex in the tree, then .
Define the score of a permutation to be where is the absolute value of . 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 and (, ) indicating the size of the tree and the root.
For the following lines, the -th line contains two integers and () indicating an edge connecting vertex and 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 .
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: , and . Their scores are , and respectively so the answer is .
For the second sample test case, there is only one good permutation: . It's score is .