[R75E]网络重启 - 代码源竞赛平台

时空限制

2S/256M

题目描述

一套中继网络由 $n$ 个中继站和 $m$ 条双向线路组成。中继站编号为 $1$ 到 $n$，整个网络连通。中继站 $i$ 的启动需求与启动后能够提供的功率均为正整数 $a_i$。

选择一个中继站 $s$ 作为重启起点时，它会被直接启动。设当前已启动的中继站集合为 $S$，初始时 $S=\{s\}$。此后可以反复进行以下操作：

• 选择一个尚未启动、并且通过至少一条线路与 $S$ 中某个中继站相连的中继站 $v$；
• 当$$a_v\le\sum_{u\in S}a_u$$ 时，将 $v$ 启动并加入 $S$。

启动新的中继站不会消耗已有功率；操作完成后，当前功率总和增加 $a_v$。

如果存在一种启动顺序，能够从 $s$ 出发启动全部 $n$ 个中继站，则称 $s$ 是合法起点。每个起点都需要从只启动自身的状态独立判断。

请你求出合法起点的数量。

格式

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示中继站 $u$ 与 $v$ 之间有一条双向线路。

输出格式

输出一个整数，表示合法起点的数量。

样例

样例输入 #1

6 5
4 4 4 4 15 10
1 2
2 3
3 4
4 5
5 6

样例输出 #1

5

样例解释 #1

从中继站 $1,2,3,4$ 中任意一个出发，都可以先启动前四个中继站，使功率总和达到 $16$，再依次启动中继站 $5,6$；从中继站 $5$ 出发也可以启动整个网络。

从中继站 $6$ 出发时，唯一相邻的中继站 $5$ 的启动需求为 $15$，大于当前功率 $10$，因此无法继续。合法起点共有 $5$ 个。

样例输入 #2

3 2
2 2 4
1 2
2 3

样例输出 #2

3

样例解释 #2

启动条件允许需求恰好等于当前功率。例如从中继站 $1$ 出发，可以先启动中继站 $2$，再在总功率为 $4$ 时启动中继站 $3$。

样例输入 #3

1 0
7

样例输出 #3

1

样例解释 #3

唯一的中继站在开始时就已经启动，因此它是合法起点。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$15$	$2 \times 10^5$	特殊性质 A
$2$	$25$	$200$	无
$3$	$60$	$2 \times 10^5$

特殊性质 A：所有 $a_i$ 相等。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$n - 1 \le m \le \min(2 \times 10^5, n(n - 1)/2)$，$1 \le a_i \le 10^9$；每条边的两个端点 $u, v$ 满足 $1 \le u, v \le n$ 且 $u \ne v$，输入图连通且没有重边。