题目描述

配点：$800$ 点
$N$頂点$N-1$辺の連結であるグラフ、つまり、「木」が与えられます。辺 $i$ は頂点 $u_i$ と $v_i$ を結んでいます。
E869120は以下のような操作を行えなくなるまで繰り返します。

• 隣り合った頂点に動く。ただし、同じ頂点を2度通ってはいけない。
• 動ける頂点がない場合、そこで操作は終了となる。
• どこに動くかは等確率にランダムに選ぶ。つまり、次に動ける頂点が$p$個である場合、それぞれの頂点に$1/p$の確率で動くことになる。

最初、頂点 $i$ にE869120君がいるとき、動く回数の期待値をすべての $i$ に対して計算しなさい。

5
1 2
2 3
3 4
4 5

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

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

2
1 2

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

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

4
1 2
2 3
2 4

2.0
1.0
2.0
2.0

3.0
1.5
3.0
1.5

4.0
2.0
2.0
2.0
4.0

2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000

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

1.0
1.0

提示

制約

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

小課題

小課題1 [ $190$点 ]

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

小課題2 [ $220$ 点 ]

• $1\ \le\ N\ \le\ 1000$

小課題3 [ $390$ 点 ]

• 追加の制約はない。