E - Skiing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

AtCoder スキー場には広場 1 、広場 2 、\ldots 、広場 N の N 個の広場があり、広場 i の標高は H_i です。 また、2 つの広場を双方向に結ぶ M 本の坂があり、i (1 \leq i \leq M) 本目の坂は広場 U_i と広場 V_i を双方向に結んでいます。どの 2 つの広場の間もいくつかの坂を使って移動することができます。

高橋君は坂を使うことによってのみ広場の間を移動でき、坂を通るごとに楽しさが変化します。具体的には広場 X と広場 Y を直接結ぶ坂を使って広場 X から広場 Y まで移動したとき次のように楽しさが変化します。

  • 広場 X が広場 Y より標高が真に高い場合、その標高差、すなわち H_X-H_Y だけ楽しさが増加する。
  • 広場 X が広場 Y より標高が真に低い場合、その標高差の 2 倍、すなわち 2(H_Y-H_X) だけ楽しさが減少する。
  • 広場 X と広場 Y の標高が等しい場合、楽しさは変化しない。

楽しさは負の値になることもあります。

最初、高橋君は広場 1 におり、楽しさは 0 です。 高橋君はいくつかの坂（ 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)
  • i \neq j ならば (U_i,V_i) \neq (U_j, V_j)
  • 入力はすべて整数である。
  • どの 2 つの広場の間もいくつかの坂を使って移動することができる。

入力

入力は以下の形式で標準入力から与えられる。

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

一度も移動を行わない時、楽しさが最大となります。

Score : 500 points

Problem Statement

AtCoder Ski Area has N open spaces called Space 1, Space 2, \ldots, Space N. The altitude of Space i is H_i. There are M slopes that connect two spaces bidirectionally. The i-th slope (1 \leq i \leq M) connects Space U_i and Space V_i. It is possible to travel between any two spaces using some slopes.

Takahashi can only travel between spaces by using slopes. Each time he goes through a slope, his happiness changes. Specifically, when he goes from Space X to Space Y by using the slope that directly connects them, his happiness changes as follows.

  • If the altitude of Space X is strictly higher than that of Space Y, the happiness increases by their difference: H_X-H_Y.
  • If the altitude of Space X is strictly lower than that of Space Y, the happiness decreases by their difference multiplied by 2: 2(H_Y-H_X).
  • If the altitude of Space X is equal to that of Space Y, the happiness does not change.

The happiness may be a negative value.

Initially, Takahashi is in Space 1, and his happiness is 0. Find his maximum possible happiness after going through any number of slopes (possibly zero), ending in any space.

Constraints

  • 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.
  • All values in input are integers.
  • It is possible to travel between any two spaces using some slopes.

Input

Input is given from Standard Input in the following format:

N M
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

4 4
10 8 12 5
1 2
1 3
2 3
3 4

Sample Output 1

3

If Takahashi takes the route Space 1 \to Space 3 \to Space 4, his happiness changes as follows.

  • When going from Space 1 (altitude 10) to Space 3 (altitude 12), it decreases by 2\times (12-10)=4 and becomes 0-4=-4.
  • When going from Space 3 (altitude 12) to Space 4 (altitude 5), it increases by 12-5=7 and becomes -4+7=3.

If he ends the travel here, the final happiness will be 3, which is the maximum possible value.

Sample Input 2

2 1
0 10
1 2

Sample Output 2

0

His happiness is maximized by not moving at all.