D - Driving on a Tree 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

Max Score: $800$ Points

Problem Statement

There is an undirected connected graph with $N$ vertices and $N-1$ edges. The i-th edge connects u_i and v_i.

E869120 the coder moves in the graph as follows:
  • He move to adjacent vertex, but he can't a visit vertex two or more times.
  • He ends move when there is no way to move.
  • Otherwise, he moves randomly. (equal probability) If he has $p$ way to move this turn, he choose each vertex with $1/p$ probability.
Calculate the expected value of the number of turns, when E869120 starts from vertex i, for all i (1 ≤ i ≤ N).

Input

The input is given from standard input in the following format. 

N
u_1 v_1
u_2 v_2
 :
u_{N-1} v_{N-1}

Output

In i-th (1 ≤ i ≤ N) line, print the expected vaule of the number of turns E869120 moves.
The relative error or absolute error of output should be within 10^{-6}.

Constraints

  • $1 \le N \le 150,000$
  • The graph is connected.

Subtasks

Subtask 1 [ $190$ points ]

  • There is no vertex which degree is more than 2.
  • This means the graph looks like a list.

Subtask 2 [ $220$ points ]

  • 1 ≤ N ≤ 1000.

Subtask 3 [ $390$ points ]

  • There are no additional constraints.

Sample Input 1

4
1 2
2 3
2 4

Sample Output 1

2.0
1.0
2.0
2.0

Sample Input 2

4
1 2
2 4
4 3

Sample Output 2

3.0
1.5
3.0
1.5

Sample Input 3

5
1 2
2 3
3 4
4 5

Sample Output 3

4.0
2.0
2.0
2.0
4.0

Sample Input 4

7
1 2
1 3
2 4
2 5
3 6
3 7

Sample Output 4

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000

Sample Input 5

12
1 2
2 3
2 4
4 5
5 6
5 7
6 8
8 9
2 10
10 11
11 12

Sample Output 5

3.666666666667
2.250000000000
3.666666666667
2.833333333333
2.555555555556
2.666666666667
4.333333333333
2.666666666667
5.333333333333
2.500000000000
2.500000000000
5.000000000000

Sample Input 6

2
1 2

Sample Output 6

1.0
1.0
配点：$800$ 点

問題文

$N$頂点$N-1$辺の連結であるグラフ、つまり、「木」が与えられます。辺 i は頂点 u_i と v_i を結んでいます。
E869120は以下のような操作を行えなくなるまで繰り返します。
  • 隣り合った頂点に動く。ただし、同じ頂点を2度通ってはいけない。
  • 動ける頂点がない場合、そこで操作は終了となる。
  • どこに動くかは等確率にランダムに選ぶ。つまり、次に動ける頂点が$p$個である場合、それぞれの頂点に$1/p$の確率で動くことになる。
最初、頂点 i にE869120君がいるとき、動く回数の期待値をすべての i に対して計算しなさい。

入力

入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
 :
u_{N-1} v_{N-1}

出力

  • $i$行目に、頂点$i$から出発した場合の動く回数の期待値を出力しなさい。
  • ただし、絶対誤差もしくは相対誤差は$10^{-6}$以内でなければなりません。

制約

  • $1 \le N \le 150,000$
  • 与えられるグラフは連結である。

小課題

小課題1 [ $190$点 ]

  • 与えられるグラフは線のようになっている。つまり、どの頂点からも辺が$3$本以上出ていることはない。

小課題2 [ $220$ 点 ]

  • $1 \le N \le 1000$

小課題3 [ $390$ 点 ]

  • 追加の制約はない。

入力例1

4
1 2
2 3
2 4

出力例1

2.0
1.0
2.0
2.0

入力例2

4
1 2
2 4
4 3

出力例2

3.0
1.5
3.0
1.5

入力例3

5
1 2
2 3
3 4
4 5

出力例3

4.0
2.0
2.0
2.0
4.0

入力例4

7
1 2
1 3
2 4
2 5
3 6
3 7

出力例4

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000

入力例5

12
1 2
2 3
2 4
4 5
5 6
5 7
6 8
8 9
2 10
10 11
11 12

出力例5

3.666666666667
2.250000000000
3.666666666667
2.833333333333
2.555555555556
2.666666666667
4.333333333333
2.666666666667
5.333333333333
2.500000000000
2.500000000000
5.000000000000

入力例6

2
1 2

出力例6

1.0
1.0