← 返回题目列表

Codeforces · 1851/G

G. 弗拉德和山脉

中文机器翻译题面 查看原题

弗拉德决定去山里旅行。他计划在 $$$n$$$ 山脉之间移动,其中一些山脉有道路相连。第 $$$i$$$ 山的高度为 $$$h_i$$$。

如果山 $$$i$$$ 和 $$$j$$$ 之间有一条路,Vlad 可以通过花费 $$$h_j - h_i$$$ 单位的能量从山 $$$i$$$ 移动到山 $$$j$$$。如果他的能量在过渡期间降至零以下,他将无法从 $$$i$$$ 山移动到 $$$j$$$ 山。请注意,$$$h_j - h_i$$$ 可以为负,然后能量将恢复。

Vlad 想要考虑不同的路线选择,因此他要求您回答以下问题:考虑到他最初拥有 $$$e$$$ 单位的能量,是否可以构建一条从山 $$$a$$$ 开始并以 $$$b$$$ 结束的路线?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个数字 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — 山脉数量和山脉之间的道路数量他们分别。

第二行包含 $$$n$$$ 整数 $$$h_1, h_2, h_3, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — 山脉的高度。

接下来的 $$$m$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由道路连接的山脉的数量。保证没有道路出现两次。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

以下 $$$q$$$ 行包含三个数字 $$$a$$$、$$$b$$$ 和 $$$e$$$ ($$$1 \le a, b \le n$$$, $$$0 \le e \le 10^9$$$) - 分别是路线的初始和最终山脉以及能量值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。同样的保证适用于 $$$m$$$ 和 $$$q$$$。

输出

对于每个查询,如果 Vlad 可以构建从山 $$$a$$$ 到山 $$$b$$$ 的路线,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

在下面的示例中,不同测试用例的答案用空行分隔,您不需要输出。

示例

输入 #1

2
7 7
1 5 3 4 2 4 1
1 4
4 3
3 6
3 2
2 5
5 6
5 7
5
1 1 3
6 2 0
4 7 0
1 7 4
1 7 2
6 5
4 7 6 2 5 1
1 3
5 3
1 5
2 4
6 2
5
1 5 1
1 3 1
1 2 1000
6 2 6
6 2 5

输出 #1

YES
NO
YES
YES
NO

YES
NO
NO
YES
NO

输入 #2

2
3 2
1 3 9
1 2
2 3
5
1 1 1
3 2 2
1 1 2
3 3 0
1 2 1
3 3
1 4 1
1 2
2 3
1 3
5
3 3 9
1 3 6
1 1 2
3 3 6
3 3 4

输出 #2

YES
YES
YES
YES
NO

YES
YES
YES
YES
YES

输入 #3

1
6 10
7 9 2 10 8 6
4 2
6 1
4 5
3 5
6 4
1 3
2 6
6 5
1 2
3 6
5
4 4 8
3 3 1
5 5 9
2 1 7
6 6 10

输出 #3

YES
YES
YES
YES
YES