BZOJ 3545 带权限。
考虑离线，把所有边按照从小到大的顺序排序，把所有询问也按照从小到大的顺序排序，然后维护一个并查集和一个权值线段树，每处理一个询问就把比这个询问的$x$更小的边连上，具体来说就是合并两个并查集以及两棵线段树，查询的时候在线段树上走一走就好了。
要注意查询的第$k$大不是第$k$小，所以顺便再维护一个$siz$，如果$siz < k$那答案即为$-1$。
时间复杂度$O((m + q)logn)$。
Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
const int M = 5e5 + ;
const int inf = << ; int n, m, qn, a[N], mn = , mp[N], ufs[N], siz[N]; struct Innum {
int val, id; friend bool operator < (const Innum &x, const Innum &y) {
if(x.val == y.val) return x.id < y.id;
else return x.val < y.val;
} } in[N]; struct Pathway {
int u, v, val; friend bool operator < (const Pathway &x, const Pathway &y) {
return x.val < y.val;
} } path[M]; struct Querys {
int pos, val, k, id, res; friend bool operator < (const Querys &x, const Querys &y) {
return x.val < y.val;
} } q[M]; inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void chkMax(int &x, int y) {
if(y > x) x = y;
} inline void discrete() {
sort(in + , in + + n);
in[].val = -inf;
for(int cnt = , i = ; i <= n; i++) {
if(in[i].val != in[i - ].val) ++cnt;
chkMax(mn, cnt);
a[in[i].id] = cnt;
mp[cnt] = in[i].val;
}
} namespace PSegT {
struct Node {
int lc, rc, sum;
} s[N * ]; int root[N], nodeCnt = , top = , pool[N * ]; #define lc(p) s[p].lc
#define rc(p) s[p].rc
#define sum(p) s[p].sum
#define mid ((l + r) >> 1) inline void push(int x) {
pool[++top] = x;
} inline int newNode() {
if(top) return pool[top--];
else return ++nodeCnt;
} void ins(int &p, int l, int r, int x) {
if(!p) p = newNode();
++sum(p);
if(l == r) return; if(x <= mid) ins(lc(p), l, mid, x);
else ins(rc(p), mid + , r, x);
} int go(int p, int l, int r, int x) {
if(l == r) return sum(p); if(x <= mid) return go(lc(p), l, mid, x);
else return go(rc(p), mid + , r, x);
} int query(int p, int l, int r, int k) {
if(l == r) return mp[l];
int now = sum(lc(p)); if(k <= now) return query(lc(p), l, mid, k);
else return query(rc(p), mid + , r, k - now);
} int merge(int u, int v, int l, int r) {
if(!u || !v) return u + v; int p = newNode();
if(l == r) sum(p) = sum(u) + sum(v);
else {
lc(p) = merge(lc(u), lc(v), l, mid);
rc(p) = merge(rc(u), rc(v), mid + , r);
sum(p) = sum(lc(p)) + sum(rc(p));
} push(u), push(v);
return p;
} } using namespace PSegT; inline void init() {
for(int i = ; i <= n; i++) {
ufs[i] = i;
siz[i] = ;
ins(root[i], , mn, a[i]);
}
} int find(int x) {
return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
} inline void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == fy) return;
root[fx] = merge(root[fx], root[fy], , mn);
ufs[fy] = fx;
siz[fx] += siz[fy]; /* for(int i = 1; i <= mn; i++)
printf("%d ", go(root[fx], 1, mn, i));
printf("\n"); */
} int main() {
read(n), read(m), read(qn);
for(int i = ; i <= n; i++) {
read(a[i]);
in[i].val = a[i], in[i].id = i;
}
for(int i = ; i <= m; i++)
read(path[i].u), read(path[i].v), read(path[i].val);
for(int i = ; i <= qn; i++)
read(q[i].pos), read(q[i].val), read(q[i].k), q[i].id = i; sort(path + , path + + m), sort(q + , q + + qn); /* printf("\n");
for(int i = 1; i <= m; i++)
printf("%d %d %d\n", path[i].u, path[i].v, path[i].val);
printf("\n");
for(int i = 1; i <= qn; i++)
printf("%d %d %d\n", q[i].pos, q[i].val, q[i].k);
printf("\n"); */ discrete();
init(); /* for(int i = 1; i <= n; i++)
printf("%d ", a[i]);
printf("\n"); */ for(int j = , i = ; i <= qn; i++) {
for(; j <= m && path[j].val <= q[i].val; ++j)
merge(path[j].u, path[j].v);
int now = find(q[i].pos); /* for(int k = 1; k <= mn; k++)
printf("%d ", go(root[now], 1, mn, k));
printf("\n"); */ if(q[i].k > siz[now]) q[q[i].id].res = -;
else q[q[i].id].res = query(root[now], , mn, siz[now] - q[i].k + );
} for(int i = ; i <= qn; i++)
printf("%d\n", q[i].res); return ;
}