AT_abc237_e [ABC237E] Skiing

AtCoder 滑雪场有 $N$ 个广场，分别为广场 $1$、广场 $2$、$\ldots$、广场 $N$，其中广场 $i$ 的海拔高度为 $H_i$。此外，有 $M$ 条双向坡道，每条坡道连接两个广场，第 $i$ 条坡道连接广场 $U_i$ 和广场 $V_i$。任意两个广场之间都可以通过若干条坡道互相到达。 高桥君只能通过坡道在广场之间移动，每经过一条坡道，**快乐值**会发生变化。具体来说，当他从广场 $X$ 通过直接连接的坡道移动到广场 $Y$ 时，快乐值的变化如下： - 如果广场 $X$ 的海拔严格高于广场 $Y$，则快乐值增加 $H_X-H_Y$。 - 如果广场 $X$ 的海拔严格低于广场 $Y$，则快乐值减少 $2(H_Y-H_X)$。 - 如果广场 $X$ 和广场 $Y$ 的海拔相等，则快乐值不变。 快乐值可以为负数。 最开始，高桥君在广场 $1$，快乐值为 $0$。他可以经过若干条（也可以一条都不经过）坡道移动，最后停留在任意一个广场。请你求出他最终可能获得的最大快乐值。

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

输出一个整数，表示高桥君最终可能获得的最大快乐值。

## 限制条件 - $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)$ - 所有输入均为整数。 - 任意两个广场之间都可以通过若干条坡道互相到达。 ## 样例解释 1 从广场 $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 如果一次也不移动，快乐值就是最大值。 由 ChatGPT 4.1 翻译