LCC/Moose '20 Contest 1 S5 - Alan's Walk

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types

Alan is bored, so he decided he would go for a walk through his mansion. Since Alan is a computer science expert, he modelled his mansion as a tree with N nodes, where nodes are rooms and edges are corridors.

Since Alan is indecisive, he will use randomness to determine where he starts, and to where he proceeds from each room. Specifically:

He will generate an integer uniformly at random from 1 to N, and start at the node.

When standing in a room, Alan can choose to stop at this room or to go to any unvisited node adjacent to this room (he doesn't like to be repetitive). Out of all these choices, he will pick one uniformly at random. For example if there are 3 adjacent unvisited nodes, he travels to each of them with a \frac{1}{4} chance, and has a \frac{1}{4} chance of stopping at the current node.

It can be proven that this process will always stop.

Alan now wants to know what the chance is that he will end up at each room from 1 to N, after the walk. Can you help him?

Input Specification

The first line will contain one integer N\ (1 \leq N \leq 10^6), the number of rooms in Alan's mansion.

The next N-1 lines will contain 2 integers A and B\ (1 \leq A,B \leq N, A \neq B), indicating a corridor between rooms A and B.

It is guaranteed the input forms a tree.

Output Specification

On one line you are to print N decimal numbers, the chance that Alan will end up in room i for each i. Your answer will be judged as correct if all of your values are within 10^{-9} absolute error.

Subtasks

Subtask 1 (30%)

N \leq 5000

Subtask 2 (70%)

No further constraints.

Sample Input 1

3
1 2
2 3

Sample Output 1

0.36111111111 0.27777777778 0.36111111111

Sample Explanation

If we start at 1, there is a \frac{1}{2} chance we stop at 1. Thus the chance of taking the walk (1) is \frac{1}{6}.

If we start at 1, there is a \frac{1}{2} chance we go to 2, from which there is a \frac{1}{2} chance we stop at 2. Thus the chance of taking the walk (1) \to (2) is \frac{1}{12}.

If we start at 1, there is a \frac{1}{2} chance we go to 2, from which there is a \frac{1}{2} chance we go to 3, from which we are guaranteed to stop. Thus the chance of taking the walk (1) \to (2) \to (3) is \frac{1}{12}.

If we start at 2, there is a \frac{1}{3} chance we stop at 2. Thus the chance of taking the walk (2) is \frac{1}{9}.

If we start at 2, there is a \frac{1}{3} chance we go to 1, from which we are guaranteed to stop. Thus the chance of taking the walk (2) \to (1) is \frac{1}{9}.

If we start at 2, there is a \frac{1}{3} chance we go to 3, from which we are guaranteed to stop. Thus the chance of taking the walk (2) \to (3) is \frac{1}{9}.

If we start at 3, there is a \frac{1}{2} chance we stop at 3. Thus the chance of taking the walk (3) is \frac{1}{6}.

If we start at 3, there is a \frac{1}{2} chance we go to 2, from which there is a \frac{1}{2} chance we stop at 2. Thus the chance of taking the walk (3) \to (2) is \frac{1}{12}.

If we start at 3, there is a \frac{1}{2} chance we go to 2, from which there is a \frac{1}{2} chance we go to 1, from which we are guaranteed to stop. Thus the chance of taking the walk (3) \to (2) \to (1) is \frac{1}{12}.

Thus, the chance of stopping at 1 is \frac{1}{6} + \frac{1}{9} + \frac{1}{12} = \frac{13}{36} \approx 0.36111111111, the chance of stopping at 2 is \frac{1}{12} + \frac{1}{9} + \frac{1}{12} = \frac{5}{18} \approx 0.27777777778, and the chance of stopping at 3 is \frac{1}{12} + \frac{1}{9} + \frac{1}{6} = \frac{13}{36} \approx 0.36111111111.

Sample Input 2

5
1 2
2 3
3 5
2 4

Sample Output 2

0.22222222222 0.15555555556 0.17500000000 0.22222222222 0.22500000000

Comments

There are no comments at the moment.