CF101D Castle

Gerald 现在位于一座古老的城堡中，这座城堡由 $n$ 个大厅和 $n-1$ 条走廊连接而成。从任意一个大厅到另一个大厅恰好只有一条路径。因此，这张图是一棵树。最初，在时间 $0$ 时刻，Gerald 位于 $1$ 号大厅。此外，城堡中的某个其他大厅藏有 Gerald 正在寻找的宝藏。宝藏的位置未知，它等概率地可能出现在其他 $n-1$ 个大厅中的任意一个。只有当 Gerald 进入藏有宝藏的大厅时，他才能发现宝藏，这一时刻即被视为他达成目标的时刻。 每条走廊的长度各不相同。与此同时，走廊很长，而大厅很小且光线充足，因此可以忽略 Gerald 在大厅中所花费的时间。由于城堡非常古老，每当某条走廊被人第二次经过时（无论方向），这条走廊就会坍塌。 Gerald 可以通过走廊在城堡中移动，直到找到宝藏为止。自然地，Gerald 希望尽快找到宝藏。换句话说，他希望采取一种策略，使得找到宝藏的平均时间尽可能小。由于每条走廊最多只能经过两次，因此 Gerald 必须选择一种能够确保访问到每个大厅的策略。 更正式地说，如果宝藏位于第二个大厅，那么 Gerald 第一次进入第二个大厅的时刻记为 $t_2$，他就会发现宝藏。如果宝藏在第三个大厅，Gerald 第一次进入第三个大厅的时刻记为 $t_3$，他就会发现宝藏。以此类推。因此，找到宝藏的平均时间等于 $$ \frac{t_2 + t_3 + \cdots + t_n}{n-1} $$

第一行包含一个整数 $n$（$2 \leq n \leq 10^{5}$），表示城堡中的大厅数量。接下来的 $n-1$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $t_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq t_i \leq 1000$），表示第 $i$ 条走廊连接了 $a_i$ 号大厅和 $b_i$ 号大厅，且通过该走廊需要花费 $t_i$ 的时间。最初 Gerald 位于 $1$ 号大厅。保证任意两个大厅之间都可以通过走廊连通。

输出一个实数，表示找到宝藏所需时间的期望值。答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$。

在第一个测试样例中，城堡只有两个大厅，因此宝藏一定在第二个大厅。Gerald 只需花费一分钟从第一个大厅走到第二个大厅。 在第二个测试样例中，Gerald 只能按照第一个大厅，第三个大厅，第二个大厅，第四个大厅的顺序访问，时间分别为 $2$ 分钟，$5$ 分钟，$7$ 分钟，平均时间是 $\frac{2+5+7}{3}=\frac{14}{3}$。 在第三个测试样例中，Gerald 需要访问 $4$ 个大厅：第二、第三、第四和第五号大厅。它们都只能从第一个大厅到达。因此，他需要依次前往这 $4$ 个大厅并返回。Gerald 会在一分钟后进入第一个大厅，在三分钟后进入第二个，在五分钟后进入第三个，在七分钟后进入第四个。平均时间为 $4$ 分钟。 由 ChatGPT 4.1 翻译