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$

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

2 1
0 10
1 2

输出 #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$
• 若 $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 翻译