← 返回题目列表

AtCoder · abc237_e

H. 滑雪

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

分数: 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

他的幸福感通过完全不动而最大化。