旅程

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个城市和 $n-1$ 条双向道路，任意两个城市之间都可以互相到达，因此这些城市和道路构成一棵树。

旅行从城市 $1$ 开始。每当马到达一个城市时，它会在所有尚未访问过的相邻城市中等概率选择一个并前往；如果不存在这样的城市，旅行就结束。每条道路的长度均为 $1$。

求旅行长度的期望值。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示城市 $u$ 与城市 $v$ 之间有一条道路。输入保证这些道路构成一棵树。

输出格式

输出一个实数，表示旅行长度的期望值。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例输入 1

4
1 2
1 3
2 4

样例输出 1

1.500000000000000

样例输入 2

5
1 2
1 3
3 4
2 5

样例输出 2

2.000000000000000

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le u,v\le n$，输入图是一棵树。