CF437D The Child and Zoo

当然我们的孩子喜欢在动物园散步。动物园有 $n$ 个区域，编号从 $1$ 到 $n$。第 $i$ 个区域里有 $a_{i}$ 只动物。此外，动物园里有 $m$ 条道路，每条道路连接两个不同的区域。动物园本身是连通的，也就是说，利用这些道路可以从任意一个区域到达任意另一个区域。 我们的孩子非常聪明。假设他想从区域 $p$ 走到区域 $q$。他会考虑从 $p$ 到 $q$ 的所有简单路径。对于每一条路径，他会写下该路径上所有区域中动物数量的最小值。我们记这些数中最大的为 $f(p,q)$。最后，孩子会选择一条使他记录下 $f(p,q)$ 的路径。 孩子参观完动物园以后，他思考了一个问题：所有 $p,q$（$p \ne q$）对下的 $f(p,q)$ 的平均值是多少？你能帮他回答这个问题吗？

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$；$0 \le m \le 10^5$）。 第二行包含 $n$ 个整数：$a_{1},a_{2},...,a_{n}$（$0 \le a_{i} \le 10^5$）。 接下来的 $m$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$1 \le x_{i},y_{i} \le n$；$x_{i} \ne y_{i}$），表示一条连接区域 $x_{i}$ 和 $y_{i}$ 的道路。 所有道路均为双向，每对区域之间最多只存在一条道路。

输出一个实数，表示 $\text{average}=\frac{\sum_{p\ne q} f(p,q)}{n(n-1)}$。 如果你的答案的相对误差或绝对误差不超过 $10^{-4}$，则被认为是正确的。

考虑第一个样例。有 $12$ 种不同的情况： - $p=1,q=3,f(p,q)=10$。 - $p=2,q=3,f(p,q)=20$。 - $p=4,q=3,f(p,q)=30$。 - $p=1,q=2,f(p,q)=10$。 - $p=2,q=4,f(p,q)=20$。 - $p=4,q=1,f(p,q)=10$。 另外 $6$ 种情况与上述对称。平均值为 $\frac{150}{12} = 12.5$。 再看第二个样例。有 $6$ 种不同的情况： - $p=1,q=2,f(p,q)=10$。 - $p=2,q=3,f(p,q)=20$。 - $p=1,q=3,f(p,q)=10$。 另外 $3$ 种情况与上述对称。平均值为 $\frac{80}{6} \approx 13.3333$。 由 ChatGPT 5 翻译