CF839C Journey

## 问题描述 在七大王国里有 $n$ 个城市和 $n-1$ 条道路，每条道路连接两个城市，并且通过这些道路我们可以从任何一个城市到达任何一个城市。 席恩和阿莎在第一个城市骑上马，他们要通过这些路开始一次旅行。但是有雾，所以他们看不见他们的马带他们去了哪里。当马抵达一个城市的时候（包括第一个城市），它会去跟当前这个城市相连的城市。但是这是一匹奇怪的马，它只去他们以前没有去过的城市。在每个城市，马以相同的概率移动去上述符合要求的城市，并且当没有这样的城市（可走）时，马就停下了。 每条路的长度都是 $1$，旅行从城市 $1$ 开始，问这次旅行的期望长度（旅行长度的期望值）是多少？你可以通过[这个链接](https://en.wikipedia.org/wiki/Expected\_value)来阅读一些关于期望（平均）值的文字。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$）——城市的数量。 下来是 $n-1$ 行，这些行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \not = v_i$）——第 $i$ 条边连接的城市。 保证通过这些道路可以从任何一个城市到达任何一个城市。

输出一个数——这次旅行长度的期望值。旅行从城市 $1$ 开始。 当你的答案的绝对或相对误差不超过 $10^{-6}$ 时你的答案将会被接受。 换句话说，假定你的答案是 $a$，标准答案是 $b$，当 $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$ 时你的答案将会被接受。

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