Skiing

题目描述

AtCoder 滑雪场有 $N$ 个称为 Space $1$, Space $2$, $\ldots$, Space $N$ 的空地。空地 $i$ 的海拔是 $H_i$。 有 $M$ 条双向连接两个空地的坡道。第 $i$ 条坡道 $(1 \leq i \leq M)$ 连接 Space $U_i$ 和 Space $V_i$。可以通过一些坡道在任意两个空地之间移动。 Takahashi 只能通过使用坡道在空地之间移动。每次他经过一条坡道，他的 happiness 会发生变化。具体地，当他通过直接连接空间 $X$ 和 $Y$ 的坡道从 Space $X$ 到 Space $Y$ 时，他的快乐变化如下。

如果 Space $X$ 的海拔严格高于 Space $Y$，快乐 增加 它们的差：$H_X-H_Y$。 如果 Space $X$ 的海拔严格低于 Space $Y$，快乐 减少 它们的差的两倍： $2(H_Y-H_X)$。 如果 Space $X$ 和 Space $Y$ 的海拔相等，快乐不变。

快乐值可能为负值。 最初，Takahashi 在 Space $1$，他的快乐为 $0$。在经过任意数量的坡道（可以为零）、并以任意空地结束后，求他能获得的最大可能快乐。

输入格式

输入由标准输入按以下格式提供： $N$ $M$ $H_1$ $H_2$ $\ldots$ $H_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

输出答案。

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

3

2 1
0 10
1 2

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$。 输入中的所有数值均为整数。 可以通过一些坡道在任意两个空地之间移动。如果 Takahashi 走路线 Space $1$ $\to$ Space $3$ $\to$ Space $4$，他的快乐变化如下。

当从 Space $1$（海拔 $10$）到 Space $3$（海拔 $12$）时，减少了 $2\times (12-10)=4$，变为 $0-4=-4$。 当从 Space $3$（海拔 $12$）到 Space $4$（海拔 $5$）时，增加了 $12-5=7$，变为 $-4+7=3$。

如果他在此结束旅行，最终快乐将是 $3$，这是可能的最大值。
他的快乐也可以通过不移动来最大化。

标签: AtCoder|abc237E

来源

AtCoder|abc237E