1136: 旅行

新火星一共有 $n$ 个城市和 $n-1$ 条道路，每条道路连接两个城市，长度均为 $1$ , 并且通过这些道路我们可以从任何一个城市到达任何一个城市。

Icefox和XHRlyb从城市 $1$ 出发，沿着这些道路旅行，每当他们游历完一个城市后，就会选择一个与当前城市相连并且还没有去过的城市继续旅行。在每个城市，它们都会以相同的概率移动去上述符合要求的城市，并且当没有这样的城市可走时他们的旅行就结束了。请问他们这次旅行的期望长度是多少呢？

Hint: （以下截图自维基百科）

第一行一个正整数 $n$ , 表示城市的数量。

接下来 $n-1$ 行，每行两个整数 $x,y$ , 表示一条道路连接城市 $x$ 和城市 $y$ 。

保证通过这些道路可以从任何一个城市到达任何一个城市。

一个数，表示这次旅行长度的期望值。旅行从城市 $1$ 开始。

当你的答案的绝对或相对误差不超过 $10^{-6}$ 时你的答案将会被接受。

换句话说，假定你的答案是 $a$，标准答案是 $b$，当 $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$ 时你的答案将会被接受。

text 4 1 2 1 3 2 4

text 5 1 2 1 3 3 4 2 5

text 1.500000000000000

text 2.000000000000000

对于 10% 的数据，$1\leq n\leq 10$

对于 30% 的数据，$1\leq n\leq 1000$

对于另外 20% 的数据，保证数据是一条链

对于另外 20% 的数据，保证树是一颗以 $1$ 为根的满二叉树

对于 100% 的数据，保证 $1\leq n\leq 10^5$

说明

在第一个例子中，他们的旅行可能以同等的概率停止于城市 $3$ 或城市 $4$。去城市 $3$ 的距离是 $1$，去城市 $4$ 的距离是 $2$，所以期望是 $1.5$。

在第二个例子中，他们的旅行可能停止于城市 $4$ 或城市 $5$。去这些城市的距离都是 $2$，所以期望是 $2$ 。

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！