Rainwater on a Tree
Time limit1sMemory limit512 MB
Water starts at the root and each vertex sends 1 unit per second to a uniformly random child; find the average expected final water over vertices that hold any water.
- Level
Medium7 of 10
- Topics
- Tree, Probability, DFS, Math
- Solved
- No attempts yet
Problem
\
A tree is a connected graph with no cycles. The figure above shows a tree whose root is vertex 1.
This tree is the one Younghoon grows in his backyard. It rained yesterday, so vertex 1 of the tree holds W units of water. Every vertex other than vertex 1 holds no water yet.
Now, every second, every vertex repeats the following operations in order.
- If it holds water and has at least one child, it picks one child and gives it 1 unit of water. If it has several children, it picks one of them with equal probability.
- If its parent sent water down to it, it receives the water and stores it.
The operations happen in order, so a vertex cannot pass water it just received from its parent to a child immediately.
Watching the tree, Younghoon wonders how much water each vertex will hold once the water stops moving. Let Pi be the expected amount of water accumulated at vertex i when the water no longer moves. What is the average of the Pi over all vertices whose Pi is greater than 0?
Input
The first line gives the number of vertices in the tree N and the integer W, the amount of water held at vertex 1. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 10^9)
The next N-1 lines give the edges of the tree in the form U V. (1 ≤ U, V ≤ N, U ≠ V)
This means the tree has an edge whose endpoints are U and V.
The input tree is always a valid connected tree, and its root is always vertex 1.
Output
Print the answer to the problem. Any value whose difference from the correct answer is at most 10^-3 is accepted.