102374: [AtCoder]ABC237 E - Skiing

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.

问题描述

AtCoder滑雪场有$N$个开放空间，称为空间1、空间2、$\ldots$、空间$N$。空间$i$的高度为$H_i$。 有$M$条双向滑雪道连接两个空间。第$i$条滑雪道（$1 \leq i \leq M$）连接空间$U_i$和空间$V_i$。可以通过一些滑雪道在任何两个空间之间旅行。

Takahashi只能通过滑雪道在空间之间旅行。每次他通过一条滑雪道，他的 幸福感 就会发生变化。具体来说，当他从空间$X$通过直接连接它们的滑雪道到达空间$Y$时，他的幸福感会如下变化。

• 如果空间$X$的高度严格高于空间$Y$的高度，幸福感 增加 为它们的差值：$H_X-H_Y$。
• 如果空间$X$的高度严格低于空间$Y$的高度，幸福感 减少 为它们的差值的两倍：$2(H_Y-H_X)$。
• 如果空间$X$的高度等于空间$Y$的高度，幸福感不变。

幸福感可能是负值。

最初，Takahashi在空间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)$ 如果 $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

如果Takahashi采取路线 Space $1$ $\to$ Space $3$ $\to$ Space $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

他的幸福感通过不移动达到最大化。