← 返回题目列表

AtCoder · s8pc_4_d

D. 在树上行驶

中文机器翻译题面 查看原题
最高分数:$800$ 积分

问题陈述

有一个无向连通图,具有 $N$ 个顶点和 $N-1$ 个边。 i第一条边连接 u_i 和 v_i.

E869120 编码器在图中的移动如下:
  • 他移动到相邻顶点,但他不能访问顶点两次或更多次。
  • 当无法移动时,他结束移动。
  • 否则,他会随机移动。 (等概率)如果他本回合有 $p$ 方式移动,他以 $1/p$ 概率选择每个顶点。
计算E869120从顶点开始时的期望匝数值 i,对于所有 i (1 ≤ i ≤ N).

输入

输入由标准输入按以下格式给出。

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