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$

输出格式

输出答案。

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

3

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

1199

提示

$1 \le N \le 2 \times 10^5$ $0 \le M \le 2 \times 10^5$ $1 \le A_i \le 10^9$ $1 \le U_i,V_i \le N$ 所给图是简单图。 输入中的所有值都是整数。通过如下操作，$N$ 次操作的代价的最大值可以为 $3$。

选择顶点 $3$。代价是 $A_1=3$。 选择顶点 $1$。代价是 $A_2+A_4=3$。 选择顶点 $2$。代价是 $0$。 选择顶点 $4$。代价是 $0$。

$N$ 次操作的代价的最大值不可能小于或等于 $2$，因此答案为 $3$。

标签: AtCoder|abc267E

来源

AtCoder|abc267E