← 返回比赛

已结束 GESP巅峰赛#29

← 上一题下一题 →

A7090 | $连通祭坛的封匣仪式$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

风祭城中散布着 $n$ 座古老祭坛，彼此由 $m$ 条无向古道相连。第 $i$ 座祭坛珍藏着 $a_i$ 份灵石。每当仪式开启，祭司会以灵石凝成“灵匣”，而每只灵匣必须 恰好 盛下 $k$ 份灵石。 你可以反复举行封匣：每次任选一片在古道上 连通 的祭坛区域，从该连通区域内若干祭坛 取走的总量 恰为 $k$，从而凝成 一只 灵匣；同时，必须把这只灵匣 指认 给该区域内 恰好一座 “匣主” 祭坛。 一地一匣 —— 每座祭坛在整个过程中 至多一次 担任匣主；但它可以在多次仪式中反复被汲取灵石。 你的任务是：在这些规则下， 最多 能封成多少只灵匣？

输入格式

- 第一行三个整数 $n,m,k$。 - 第二行 $n$ 个整数 $a_1,\dots,a_n$。 - 接下来 $m$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示一条连接 $u$ 与 $v$ 的无向古道。

输出格式

- 输出一个整数，表示最多能封成的灵匣数量。

输入输出样例

输入 #1

输出 #1

输入 #2

4 1 7
0 7 7 6
1 2

输出 #2

测试点$n,m$ 范围$k$ 范围$a_i$ 范围$1\sim 2$$2\le n,m <20$$1\le k\le 10^9$$0\le a_i\le 10^9$$3\sim 6$$20\le n,m <500$$1\le k\le 10^9$$0\le a_i\le 10^9$$7\sim 20$$500\le n,m \le 2\times10^{5}$$1\le k\le 10^9$$0\le a_i\le 10^9$

C++ 编辑器

输入

输出