AT_abc267_e [ABC267E] Erasing Vertices 2

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图（即没有自环和重边的无向图）。第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。每个顶点 $i$ 上写有一个正整数 $A_i$。 你需要重复以下操作共 $N$ 次： - 选择一个尚未被删除的顶点 $x$，并删除“顶点 $x$”以及“所有以顶点 $x$ 为端点的边”。本次操作的代价为：所有与顶点 $x$ 直接相连且尚未被删除的顶点上所写整数的总和。 将 $N$ 次操作中每次操作的代价的最大值，定义为整个操作序列的总代价。请你求出总代价可能取得的最小值。

输入以如下格式从标准输入读入。 > $N$ $M$ > $A_1$ $A_2$ $\dots$ $A_N$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$

请输出答案。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $0 \leq M \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq U_i, V_i \leq N$ - 给定的图是简单图。 - 所有输入均为整数。 ## 样例解释 1 按照如下方式进行操作，可以使 $N$ 次操作的代价中的最大值为 $3$： - 选择顶点 $3$。代价为 $A_1=3$。 - 选择顶点 $1$。代价为 $A_2+A_4=3$。 - 选择顶点 $2$。代价为 $0$。 - 选择顶点 $4$。代价为 $0$。 无法将 $N$ 次操作的最大代价降到 $2$ 以下，因此答案为 $3$。 由 ChatGPT 4.1 翻译