登山(clim)

• 输入：clim.in
• 输出：clim.out
• 时间限制：2 s
• 内存限制：256 MB

题目描述

训练营组织了一次登山拉练。共有 $n$ 座山，编号为 $1$ 到 $n$，第 $i$ 座山的高度为 $h_i$。其中一些山之间修有双向道路。

一名同学从山 $x$ 沿道路走到山 $y$ 时，需要消耗 $h_y-h_x$ 点体力。若 $h_y<h_x$，则这个值为负数，表示体力会恢复。行走过程中体力不能变为负数。

现在有 $q$ 次询问。每次询问给定起点 $a$、终点 $b$ 和初始体力 $e$，请判断是否存在一条从山 $a$ 出发并最终到达山 $b$ 的路线。每次询问互相独立。

输入格式

从文件 clim.in 中读入数据。

第一行包含两个整数 $n,m$，分别表示山的数量和道路的数量。

第二行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$，表示每座山的高度。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示山 $u$ 和山 $v$ 之间有一条双向道路。

接下来一行包含一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含三个整数 $a,b,e$，表示起点、终点和初始体力。

输出格式

输出到文件 clim.out 中。

对于每次询问，如果能够从山 $a$ 到达山 $b$，输出 YES，否则输出 NO。

样例1输入

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

样例1输出

YES
NO
YES
YES
NO

样例1解释

对于第 $3$ 次询问，从山 $4$ 出发时体力为 $0$。可以先从山 $4$ 到山 $3$，消耗 $h_3-h_4=3-4=-1$ 点体力，体力恢复为 $1$；再从山 $3$ 到山 $6$，消耗 $1$ 点体力；最后从山 $6$ 到山 $5$、山 $7$，过程中体力不会变为负数，因此可以到达。

对于第 $5$ 次询问，从山 $1$ 出发时初始体力为 $2$，无法经过高度超过 $3$ 的山，因此不能到达山 $7$。

数据范围

对于所有数据，$2 <= n <= 200000$，$1 <= m,q <= 200000$，$1 <= h_i <= 10^9$，$0 <= e <= 10^9$。保证没有自环和重边。每个测试点 $5$ 分。

特殊性质 A：保证所有山的高度相同。

特殊性质 B：保证道路形成一棵树。