最高分数:$800$ 积分
E869120 编码器在图中的移动如下:
计算E869120从顶点开始时的期望匝数值 i,对于所有 i (1 ≤ i ≤ N).
问题陈述
有一个无向连通图,具有 $N$ 个顶点和 $N-1$ 个边。 i第一条边连接 u_i 和 v_i.E869120 编码器在图中的移动如下:
- 他移动到相邻顶点,但他不能访问顶点两次或更多次。
- 当无法移动时,他结束移动。
- 否则,他会随机移动。 (等概率)如果他本回合有 $p$ 方式移动,他以 $1/p$ 概率选择每个顶点。
输入
输入由标准输入按以下格式给出。
N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
输出
In i-th (1 ≤ i ≤ N) 行,打印E869120移动圈数的期望值。输出的相对误差或绝对误差应在 10^{-6}.
约束
- $1 \le N \le 150,000$
- 该图已连接。
子任务
子任务 1 [ $190$ 点 ]
- 没有度数大于 2 的顶点。
- 这意味着图表看起来像一个列表。
子任务 2 [ $220$ 点 ]
- 1 ≤ N ≤ 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