P6992 [NEERC 2014] 隐藏迷宫

海伦和亨利是《隐藏迷宫》这档在 Hidden Land 超火的综艺节目的铁杆粉丝。节目里，两位选手（通常是一对夫妻）要在由 $n$ 个大厅组成的迷宫中飞速穿行，这些大厅通过若干条隧道相连。每条隧道连接两个不同的大厅，且任意一对大厅之间最多只有一条隧道。 比赛一开始，两位选手分别被放置在两个不同的大厅里。然后，他们要争分夺秒地赶去见面，必须在时间耗尽前相遇。穿过每条隧道时，选手会找到一张写有正整数线索的小纸条。 如果两人最终在某条隧道中相遇，并成功找到了该隧道上的线索，他们就算赢了。奖金的数额是将他们找到的所有线索排序后取中位数。游戏设计保证他们找到的线索数总是奇数。 海伦和亨利看了无数集节目，渐渐摸清了游戏的套路。他们发现迷宫结构始终不变，还画出了完整地图。后来他们发现，这个迷宫设计得很巧妙：只要每条隧道最多走一次，任意两个大厅之间就只有一条唯一的路径。 他们还听过一位名叫希拉里的工作人员讲过，这个迷宫是用下面的随机算法建造的： 步骤 $1$：先确定大厅数目 $n$，建造 $n$ 个大厅，编号从 $1$ 到 $n$。 步骤 $2$：随机选两个整数 $i$ 和 $j$，它们均匀分布在 $1$ 到 $n$ 之间。 步骤 $3$：如果大厅 $i$ 和 $j$ 是同一个，或者它们之间已经有通路了，跳转到步骤 $2$。 步骤 $4$：在大厅 $i$ 和 $j$ 之间建造一条隧道。如果此时任意两个大厅间都有通路了，结束；否则跳转到步骤 $2$。 海伦和亨利还注意到，每条隧道上的线索数值固定不变，但他们不知道线索数值是如何生成的。他们把每条隧道对应的线索值都标在了地图上。 穿过一条隧道并找到线索需要 $1$ 分钟，选手们从大厅跑到隧道中心相遇时需要半分钟。给定的时间刚好够他们以最优策略相遇——即走最短路径，不出错，且不绕路。为了让他们能在隧道中心相遇，比赛一开始两人被放在的两个大厅间的最短路径长度是奇数。 海伦和亨利想参加节目，他们对迷宫了如指掌，确信自己能以最优策略完成任务。现在，假设初始两个大厅的选择是均匀随机的，且只选那些最短路径长度为奇数的大厅对。他们想知道自己赢得奖金的期望值是多少。请帮他们算出这个期望。

第一行输入一个整数 $n (2 \le n \le 30 000)$，表示大厅数。 接下来 $n − 1$ 行，每行三个整数：$u_{i}, v_{i}, c_{i} (1 \le u_{i}, v_{i} \le n , 1 \le c_{i} \le 10^{6})$，表示第 $i$ 条隧道连接的两个大厅 $u_{i}$ 和 $v_{i}$，以及该隧道上的线索值 $c_{i}$。 迷宫保证是题目中描述的随机算法生成的。

输出一个实数，表示奖金的期望值。答案的绝对或相对误差不得超过 $10^{−9}$。

时间限制：3 秒，内存限制：256 MB。 题面翻译由 GPT-4.1-mini 提供。