分数: 500 点
问题陈述
AtCoder 滑雪场有 N 称为空间的开放空间 1,空间 2, \ldots,空间 N。太空的高度 i is H_i。 有 M 双向连接两个空间的斜坡。的 i第斜率 (1 \leq i \leq M) 连接空间 U_i 和空间 V_i。使用一些斜坡可以在任意两个空间之间移动。
高桥只能通过斜坡在空间之间移动。每次他走过斜坡时, 幸福 党的 变化。具体来说,当他从太空出发时 X 前往太空 Y 通过使用直接连接它们的斜率,他的幸福感发生如下变化。
- 如果太空的高度 X 严格高于Space Y,幸福 增加 按其差异: H_X-H_Y.
- 如果太空的高度 X 严格低于 Space Y,幸福 减少 将其差值乘以 2: 2(H_Y-H_X).
- 如果太空的高度 X 等于空间的 Y,幸福不变。
幸福感可能是负值。
最初,高桥在太空中 1,他的幸福是 0。在经历任意数量的斜坡(可能为零)、结束于任意空间后,找到他最大可能的幸福。
约束
- 2 \leq N \leq 2\times 10^5
- N-1 \leq M \leq \min( 2\times 10^5,\frac{N(N-1)}{2})
- 0 \leq H_i\leq 10^8 (1 \leq i \leq N)
- 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
- (U_i,V_i) \neq (U_j, V_j) if i \neq j.
- 输入中的所有值都是整数。
- 可以使用一些斜坡在任意两个空间之间移动。
输入
输入由标准输入按以下格式给出:
N M H_1 H_2 \ldots H_N U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
打印答案。
示例输入 1
4 4 10 8 12 5 1 2 1 3 2 3 3 4
示例输出 1
3
如果高桥选择太空路线 1 \to 空间 3 \to 空间 4,他的幸福感变化如下。
- 从太空出发时 1 (海拔高度 10) 到太空 3 (海拔高度 12),它减少 2\times (12-10)=4 并变为 0-4=-4.
- 从太空出发时 3 (海拔高度 12) 到太空 4 (海拔高度 5),它增加 12-5=7 并变为 -4+7=3.
如果他在这里结束旅行,最后的幸福将是 3,这是最大可能值。
示例输入 2
2 1 0 10 1 2
示例输出 2
0
他的幸福感通过完全不动而最大化。