AT_s8pc_4_d.Driving on a Tree

E869120 正在处理一个由 $N$ 个顶点和 $N-1$ 条边组成的树结构。对于这棵树上的每一条边 $i$，它连接着顶点 $u_i$ 和 $v_i$。在树上，E869120 可以做如下操作，直到无法继续：

• 移动到相邻的顶点上，但不能重复经过任何一个顶点。
• 如果没有可移动的顶点，操作就结束。
• 移动到哪个顶点是随机且等概率的。如果在某个顶点有 $p$ 个可移动邻居，每个邻居都有 $1/p$ 的概率被选中。

给定一棵树，当 E869120 从顶点 $i$ 出发时，求他能移动的步数的期望值。请你为所有顶点 $i$ 计算出这个期望值，精确到 $10^{-6}$。

以下为输入输出格式及示例：

输入：
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$ 行输出从顶点 $i$ 出发时移动次数的期望值。
• 要求输出结果的绝对误差或相对误差不超过 $10^{-6}$。

• $1 \le N \le 150,000$
• 题目保证图是连通的。

子任务

• 子任务 1 [190 分]: 图是一条链，即没有顶点连接超过两个邻居。
• 子任务 2 [220 分]: $1 \le N \le 1000$
• 子任务 3 [390 分]: 不具备其他额外限制条件。

本翻译由 AI 自动生成