题目链接：Problem - G - Codeforces

题目大意：

现有n座山， 每座山都有它的高度h[ i ] (第i座)，现有人去爬山， 从 山 i 到山 j 能量消耗为 h[ j ] -       h[ i] , 相当于从低山到高的山消耗能量， 从高的山到低的山恢复能量。后有q次查询问，这q次是否可以从a山到b山，给了初始能量e.

输入：

输入的第一行包含一个整数 t ( 1≤t≤1e4 )。( 1≤t≤1e4 ) - 测试用例的数量。

下面是测试用例的说明。

每个测试用例的第一行包含两个数字 n 和 m ( 2≤n≤2⋅1e5 )--分别是山的数量和山间道路的数量。

第二行包含 n 个整数 h1,h2,h3,…,hn( 1≤hi≤1e9 )--山的高度。

接下来的 m 行包含两个整数 u 和 v ( 1≤u,v≤n ， u≠vu≠v )--由一条道路连接的山脉的编号。保证没有一条道路出现两次。

下一行包含一个整数 q ( 1≤q≤2⋅1e5)--查询次数。

接下来的 q 行包含三个数字 a 、 b 和 e ( 1≤a,b≤n1≤a,b≤n 、 0≤e≤1e9)--分别是路线的初始和最终山脉以及能量。

保证所有测试用例的 n 之和不超过 2⋅1e5 。同样的保证也适用于 m 和 q 。

输出：

可以YES, 不可以NO

每个此时样例要分开。

算法： 最小生成树， 贪心， 离线查询

1.首先先看爬山的情况： 假如现有山峰高度 5，3，4，7，10   假设从高度为5的山出发，初始能量为3 ， 那么可以看出可以爬到 高度为 3，4，7的山。而爬不上高度为 10 的山。所以可以看出能否爬上另一座山主要看初始高度与开始的能量总和是否大于另一座山。（因为下山要恢复能量）

2.由此可见，在有一些道路是可以不用走的。联想到最小生成树，并且为了更好的利用以上的条件，采用离线查询的方式构建最小生成树。

3.先建立边集合，从 u山到v山，将两座山的最大值看做权值。用于后面建树时 当查询时的初始值  比该边(u,v)的权值大时说明 此时 的a山可以到u山与v山。就用并查集维护起来， 当边集为空， 或边(u,v)的权值大了，说明已经建好树，或到达不了其他山了。然后判断 a, b是否在一个连通块里。

4.建树查询的方案要先按初始能量排序，后通过比较建树。

可看代码理解

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;struct DSU{int n;vector<int> tree, sz;DSU(){}DSU(int n){innt(n);}void innt(int n){this->n = n;tree.resize(n+1);sz.assign(n+1,1);for(int i=0; i<=n; i++) {tree[i] = i;}}int find(int x){if(tree[x] != x) {int fx = find(tree[x]);tree[x] = fx;}return tree[x];}bool merge(int a,int b){a = find(a);b = find(b);if(a == b)return false;sz[a] += sz[b];tree[b] = a;return true;}bool same(int a, int b){return find(a) == find(b);}int size(int x){return sz[find(x)];}
};void solve(){int n, m;cin >> n >> m;DSU dsu = DSU(n);//并查集vector<int> h(n);for(int i=0; i<n; i++) {cin >> h[i];}//建立边集合priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> dq;for(int i=0; i<m; i++) {int u, v;cin >> u >> v;u--, v--;dq.push({max(h[v], h[u]), u, v});//取最大值，用于判断是否可以达到u, v点}int q;cin >> q;vector<array<int, 4>> quy(q);vector<bool> ans(q);for(int i=0; i<q; i++) {int a, b, e;cin >> a >> b >> e;a--, b--;quy[i] = {h[a]+e, a, b, i};//初始能量h[a]+e, i 为了方便找到原来的顺序输出}sort(quy.begin(), quy.end());for(int i=0; i<q; i++) {auto [hight, a, b, pos] = quy[i];while(!dq.empty() && dq.top()[0] <= hight) { //关键auto [_, u, v] = dq.top();dq.pop();dsu.merge(u, v);}ans[pos] = dsu.same(a, b);//判断是否可以在里面//因为并查集维护的点均是山的高度比初始能量（a）小的山}for(int i=0; i<q; i++) {if(ans[i]) {cout << "YES\n";}else{cout << "NO\n";}}cout << "\n";//换行
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while(t--) {solve();}return 0;
}

欢迎大佬指正。