← 返回题目列表

Codeforces · 839/C

C. 旅程

中文机器翻译题面 查看原题

七国中有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。