#P12450. [INOI Team Selection 2021] Maximal Tree Coloring
[INOI Team Selection 2021] Maximal Tree Coloring
题目描述
Arash's mom gave him a vertex tree as a birthday gift.
Arash has pencils in different colors, he will color the edges one by one with these pencils, for each edge, he will choose one of his pencils randomly and colors this edge with that pencil, the color of each edge is independent of colors of the other edges', and for each edge, the probability of choosing each edge is exactly .
After he finishes coloring edges, he will put edges in groups. edges and will be in the same group if and only if a series of edges exist such that:
- The first edge in the series is equal to .
- The last edge in the series is equal to .
- For all adjacent pairs of edges in the series, these two edges have a common vertex.
- All of this edges should have same color.
After coloring the tree and putting edges into groups, he will count the number of groups. What is the expected value of the number of groups?
One can prove that the answer is in the form of such that and are relatively prime numbers. You should calculate modulo and print it in the output.
输入格式
The first line of the input contains and , the number of vertices and the number of pencils.
The following lines describe the edges of the tree. The -th line contains two integers and (, ), denotes an edge between and . It is guaranteed that these edges form a tree.
输出格式
Print one integer, the answer of the question.
3 1
1 2
2 3
1
3 2
1 2
2 3
500000005
提示
Sample Explanation
In the second sample, if both edges had same color, there would be only one group and if their color were different, there would be two groups. So the expectation would be . in the form of is equal to .
Constraints
- ;
- ;
Subtasks
subtask | score | limits |
---|---|---|
1 | 11 | |
2 | 23 | |
3 | 66 | No extra limits |