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$。

There are $ n $ cities and $ n-1 $ roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads. Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities. Let the length of each road be $ 1 $ . The journey starts in the city $ 1 $ . What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link [https://en.wikipedia.org/wiki/Expected\_value](https://en.wikipedia.org/wiki/Expected_value).

The first line contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — number of cities. Then $ n-1 $ lines follow. The $ i $ -th line of these lines contains two integers $ u_{i} $ and $ v_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ u_{i}≠v_{i} $ ) — the cities connected by the $ i $ -th road. It is guaranteed that one can reach any city from any other by the roads.

Print a number — the expected length of their journey. The journey starts in the city $ 1 $ . Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Namely: let's assume that your answer is $ a $ , and the answer of the jury is $ b $ . The checker program will consider your answer correct, if .

4
1 2
1 3
2 4

1.500000000000000

5
1 2
1 3
3 4
2 5

2.000000000000000

In the first sample, their journey may end in cities $ 3 $ or $ 4 $ with equal probability. The distance to city $ 3 $ is $ 1 $ and to city $ 4 $ is $ 2 $ , so the expected length is $ 1.5 $ . In the second sample, their journey may end in city $ 4 $ or $ 5 $ . The distance to the both cities is $ 2 $ , so the expected length is $ 2 $ .