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

输入 #1

4 3
3 1 4 2
1 2
1 3
4 1

输出 #1

3

输入输出样例 #2

输入 #2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

输出 #2

1199

说明/提示

限制条件

• $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 翻译