配点 : 100 点
問題文
游乐园“Pakenland”有 有N 点, 第i 个点的海拔是 H_i 。还有,在公园里 M 有过山车轨道,i 铁轨是一个点 U_i 和 V_i 双向连接。
您想要使用其中一些轨道来构建满足以下条件的过山车路径:
- 通过点的顺序 v_0, v_1, \dots, v_n 可以表示为v_0 = v_n 成立。
- 全部 有一条轨道直接连接 i (1 \leq i \leq n),v_{i-1} 和 v_i 。
还有,过山车 有趣 使用以下公式定义 。
\[ \frac{1}{n} \sum_{i=1}^{n} \max(0, H_{v_{i-1}} - H_{v_i}) \]
找到享受的最大价值。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_{i} \lt V_{i} \leq N (1 \leq i \leq M)
- i \neq j 然后, (U_{i}, V_{i}) \neq (U_{j}, V_{j})
- 输入全部为整数
入力
输入将以以下格式从标准输入提供。
N M H_1 H_2 \ldots H_N U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
打印答案。与真实值的绝对或相对误差为 10^{-9} 以下情况被确定为正确的。 按照
入力例 1
4 5 1 2 3 4 1 2 1 3 1 4 2 3 3 4
出力例 1
1.5
例如, 4, 3, 2, 1, 4 顺序通过的过山车满足问题陈述中的条件。有趣的是 自
- H_4 - H_3 = 1
- H_3 - H_2 = 1
- H_2 - H_1 = 1
- H_1 - H_4 = -3
以来,
该值除以 (\max(0, 1) + \max(0, 1) + \max(0, 1) + \max(0, -3)) 的 4 ,即 0.75 。
采取
如果你建造了一条最大化享受的路线,它的价值将为 1.5 。
采取
入力例 2
4 2 1 1 2 3 1 2 3 4
出力例 2
0.5
游乐园中可能存在一组不仅通过轨道连接的点。