七国中有n个城市和n-1条道路,每条道路连接两个城市,我们可以通过道路从任何其他城市到达任何城市。
席恩和亚拉·葛雷乔伊在第一个城市骑马,他们开始在道路上旅行。但天气大雾,他们看不到马把他们带到哪里。当马到达一个城市(包括第一个城市)时,它会前往与当前城市相连的城市之一。但这是一匹奇怪的马,它只去它们以前没有去过的城市。在每个这样的城市中,马以相同的概率前进,当没有这样的城市时它会停下来。
设每条路的长度为1。旅程从城市开始。1.他们的旅程的预期长度(长度的期望值)是多少?您可以通过链接 https://en.wikipedia.org/wiki/Expected_value 了解预期(平均)值。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100000) — 城市数量。
接下来是 n - 1 行。这些行中的第 i 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由第 i 条道路连接的城市。
保证可以通过公路从任何其他城市到达任何城市。
输出
打印一个数字——他们的预计旅程长度。旅程从城市 1 开始。
如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 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
注意
在第一个样本中,他们的旅程可能以相同的概率在城市 3 或 4 结束。到城市 3 的距离为 1,到城市 4 的距离为 2,因此预期长度为 1.5。
在第二个样本中,他们的旅程可能在城市 4 或 5 结束。到这两个城市的距离均为 2,因此预期长度为 2。