← 返回题目列表

Codeforces · 101/D

D. 城堡

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

杰拉德位于一座古老的城堡中,该城堡由 n 个大厅和 n-1 个走廊相连。这正是从任何大厅到任何其他大厅的一种方式。因此,该图是一棵树。最初,在时间 0 时刻,杰拉德位于大厅 1。此外,城堡的其他一些大厅包含杰拉德正在寻找的宝藏。宝藏的位置未知;它可以等概率地位于任何其他 n - 1 个大厅中。杰拉德只有带着宝藏进入大厅后才能知道宝藏在哪里。杰拉德看到宝藏的那一刻被认为是实现他的目标的时刻。

走廊的长度不同。那时,走廊被认为是长的,大厅被认为是小而明亮的。因此,可以不考虑杰拉尔德在大厅里度过的时间。这座城堡很古老,所以当有人参观它两次时,无论从哪个方向,走廊都会塌陷。

杰拉德可以使用走廊在城堡周围移动;他会一直走下去,直到找到宝藏。杰拉德自然希望尽快找到它。换句话说,他想要以一种尽可能缩短找到宝藏的平均时间的方式行事。每个走廊最多可使用两次。这就是为什么杰拉德会选择这样的策略,这样他就可以肯定地参观每个大厅。

更正式地说,如果宝藏位于第二个大厅,那么杰拉德将在他第一次进入第二个大厅的那一刻找到它——让它成为时刻t2。如果宝藏在第三大厅,那么杰拉德第一次进入第三大厅就会发现它。设其为时刻t3。等等。因此,找到宝藏的平均时间将等于 $${ \frac { t _ { 2 } + t _ { 3 } + \cdots + t _ { n } } { n - 1 } }$$。

输入

第一行包含唯一的整数 n (2 ≤ n ≤ 105) — 城堡中大厅的数量。接下来的 n - 1 行每行包含三个整数。第 i 行包含数字 ai、bi 和 ti(1 ≤ ai,bi ≤ n,ai ≠ bi,1 ≤ ti ≤ 1000)——与第 i 条走廊相连的大厅数量以及沿着走廊所需的时间。最初,Gerald 位于 1 号大厅。保证可以通过走廊从任何一个大厅到达任何其他大厅。

输出

打印唯一实数:寻找宝藏所需时间的期望值。答案与正确答案相差不少于 10 - 6。

示例

输入 #1

2
1 2 1

输出 #1

1.0

输入 #2

4
1 3 2
4 2 1
3 2 3

输出 #2

4.333333333333334

输入 #3

5
1 2 1
1 3 1
1 4 1
1 5 1

输出 #3

4.0

注意

在第一个测试中,城堡只有两个大厅,这意味着宝藏位于第二个大厅。杰拉德从第一个大厅到第二个大厅只需要一分钟的时间。

在第二次测试中,杰拉德只能从第一大厅进入第三大厅。他可以从第三个房间到达第一个房间或第二个房间,但他已经参观过第一个大厅,从那里无法到达任何地方。所以,他需要前往第二大厅。他应该从那里前往 4 号大厅,因为所有其他大厅都已经参观过。如果宝藏位于第三大厅,杰拉德会在一分钟内找到它,如果宝藏位于第二大厅,杰拉德会在两分钟内找到它,如果宝藏位于第四大厅,杰拉德会在三分钟内找到它。平均时间为2分钟。

在第三次测试中,杰拉德需要参观 4 个大厅:第二、第三、第四和第五个大厅。所有这些都只能从第一个大厅到达。所以,他需要一一前往那四个大厅,然后返回。杰拉德将在一分钟内进入第一个大厅,三分钟内进入第二个大厅,五分钟内进入第三个大厅,七分钟内进入第四个大厅。平均时间为4分钟。