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 自动生成**