← 返回题目列表

Codeforces · 437/D

D. 孩子和动物园

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

我们的孩子当然喜欢在动物园里散步。动物园有 n 个区域,编号从 1 到 n。第 i 个区域包含 ai 动物。动物园里还有m条路,每条路连接两个不同的区域。当然,动物园是相连的,因此您可以通过道路从任何其他区域到达动物园的任何区域。

我们的孩子很聪明。想象一下孩子想要从 p 区到 q 区。首先,他考虑从 p 到 q 的所有简单路线。对于每条路线,孩子写下数字,该数字等于路线区域中动物的最小数量。让我们将最大的书面数字表示为 f(p, q)。最后,孩子选择其中一条路线并记下值 f(p, q)。

孩子参观完动物园后,他思考这个问题:所有对 p, q (p ≠ q) 的 f(p, q) 的平均值是多少?你能回答他的问题吗?

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105)。第二行包含 n 个整数:a1, a2, ..., an (0 ≤ ai ≤ 105)。然后m行,每行包含两个整数xi和yi(1≤xi,yi≤n;xi≠yi),表示xi和yi区域之间的道路。

所有道路都是双向的,每对区域最多由一条道路连接。

输出

输出一个实数 — $$\frac{\sum_{p,q,p\neq q} f(p,q)}{n(n-1)}$$ 的值。

如果答案的相对或绝对误差不超过 10 - 4,则认为答案是正确的。

示例

输入 #1

4 3
10 20 30 40
1 3
2 3
4 3

输出 #1

16.666667

输入 #2

3 3
10 20 30
1 2
2 3
3 1

输出 #2

13.333333

输入 #3

7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7

输出 #3

18.571429

注意

考虑第一个样本。有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例与上述对称。平均值为 $$(10+20+30+10+20+10)\times 2\over 12 \approx 16.666667$$。

考虑第二个示例。有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例与上述对称。平均值为$$(10+20+10)\times2\over6\approx13.333333$$。