rt, 调了1h+了

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 5e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
int h[N], rk[N];
vector<int> hs;
array<int, 3> edge[M];
vector<int> e[N];
int val[N], fa[N][25], p[N], L[N], R[N], dep[N];
struct DSU {
	int fa[N];
	void init() {
		for(int i = 1; i <= n * 2; i ++) fa[i] = i;
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);	
	}
} dsu;
int tot, idx;
void dfs(int u, int fath) {
	L[u] = idx;
	if(u <= n) p[++ idx] = u;
	dep[u] = dep[fath] + 1;
	fa[u][0] = fath;
	for(int i = 1; i <= __lg(dep[u]); i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u);
	R[u] = idx;
}
struct SegT {
	int l, r, val;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
} tr[N * __lg(N)];
int rt[N], cnt;
void pushup(int x) {
	val(x) = val(l(x)) + val(r(x));
}
void build(int &x, int l, int r) {
	x = ++ cnt;
	if(l == r) return;
	int mid = l + r >> 1;
	build(l(x), l, mid), build(r(x), mid + 1, r);
}
void insert(int &x, int lst, int pos, int l, int r) {
	x = ++ cnt;
	tr[x] = tr[lst];
	if(l == r) {
		val(x) ++;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) insert(l(x), l(lst), pos, l, mid);
	else insert(r(x), r(lst), pos, mid + 1, r);
	pushup(x);
}
int query(int x, int y, int l, int r, int k) {
	if(l == r) return l;
	int cnt = val(r(y)) - val(r(x)), mid = l + r >> 1;
	if(k <= cnt) return query(r(x), r(y), mid + 1, r, k);
	else return query(l(x), l(y), l, mid, k - cnt);
}
int get(int u, int x) {
	for(int i = 19; ~i; i --)
		if(val[fa[u][i]] <= x) u = fa[u][i];
	return u;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i ++) {
		cin >> h[i];
		hs.push_back(h[i]);
	}
	sort(hs.begin(), hs.end());
	hs.erase(unique(hs.begin(), hs.end()), hs.end());
	for(int i = 1; i <= n; i ++) {
		h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin() + 1;
	}
	tot = n;
	dsu.init();
	for(int i = 1; i <= m; i ++)
		cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
		if(u == v) continue;
		tot ++;
		dsu.fa[u] = dsu.fa[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = edge[i][0];
	}
	val[0] = INF;
	dfs(tot, 0);
	build(rt[0], 1, hs.size());
	for(int i = 1; i <= n; i ++) {
		insert(rt[i], rt[i - 1], h[p[i]], 1, n);
	}
	while(q --) {
		int v, x, k;
		cin >> v >> x >> k;
		v = get(v, x);
		if(R[v] - L[v] < k) cout << -1 << '\n';
		else cout << hs[query(rt[L[v]], rt[R[v]], 1, hs.size(), k) - 1] << '\n';
	}
    return 0;
}