KDH, Son of the Typhoon
Time limit2sMemory limit512 MB
On a tree where every pair of vertices adds 1 traffic to each path edge, vertices survive independently with probability p; find the expected total traffic.
- Level
Medium7 of 10
- Topics
- Tree, DFS, Probability, Combinatorics
- Solved
- No attempts yet
Problem
KDH, the son of the typhoon (the stage name is read as kkeu-deu-heu) will hold a concert at the Suwon Sports Complex near his school. The nickname says it plainly: his popularity stirs up a typhoon wherever he goes. This time the typhoon is about to sweep through Songjuk-dong.
Songjuk-dong is a single tree of points joined by roads. Gyeonggi Science High School, the KT wiz ballpark, Homeplus, Bulloman, Sulbing and every other place there are all connected to one another. Songjuk-dong is a busy neighborhood, so for each pair of two different points, every road on the path between them gains unit of traffic. The order inside a pair does not matter.
When the typhoon sweeps through Songjuk-dong, each point collapses with probability , independently of the others. If even one point on a path collapses, counting both endpoints, that path adds no traffic at all.
Less traffic means less concert revenue. Compute the expected value of the total traffic of every road in Songjuk-dong after the typhoon.
Input
The first line contains the number of points () and two integers and that describe the probability . ()
Each of the next lines contains the two points and that a road joins. (, )
The given graph is always a connected tree.
Output
On the first line, print the expected value of the total traffic of every road in Songjuk-dong after the typhoon.
Write that expected value as a fraction in lowest terms and print , where is the modular inverse of modulo .
Hint
The expected value in the first example is .