```cpp
#include <bits/stdc++.h>
using namespace std;
#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
namespace IO {
char _buf[1 << 21], *_p1 = _buf, *_p2 = _buf;
#define ch() \
(_p1 == _p2 && \
(_p2 = (_p1 = _buf) + fread(_buf, 1, 1 << 21, stdin), _p1 == _p2) \
? EOF \
: *_p1++)
inline int in() {
int s = 0, f = 1;
char x = ch();
for (; x < '0' || x > '9'; x = ch())
if (x == '-') f = -1;
for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
return f == 1 ? s : -s;
}
char buf_[1 << 21];
int p1_ = -1;
inline void flush() {
fwrite(buf_, 1, p1_ + 1, stdout);
p1_ = -1;
}
inline void pc(char x) {
if (p1_ == (1 << 21) - 1) flush();
buf_[++p1_] = x;
}
inline void out(int x) {
char k[30];
int pos = 0;
if (!x) {
pc('0');
return;
}
if (x < 0) {
pc('-');
x = -x;
}
while (x) {
k[++pos] = (x % 10) | 48;
x /= 10;
}
for (int i = pos; i; i--) pc(k[i]);
return;
}
inline void out(string x) {
int k = x.size();
for (int i = 0; i < k; i++) pc(x[i]);
}
} // namespace IO
using namespace IO;
const int A = 5e5 + 5;
const int INF = 1e9 + 5;
const int logA = 20;
int n, m, Q;
int hi[A], val[A], all;
int ex[A];
vector<int> root;
namespace Tree {
int head[A], tot_road;
struct Road {
int nex, to;
} road[2 * A];
inline void edge(int x, int y) {
road[++tot_road] = {head[x], y}, head[x] = tot_road;
}
int lg[A], f[A][logA];
int dep[A], sz[A], pos[A], idx[A], ed[A], tot;
struct SGT {
int ls, rs;
int num;
} tr[4 * logA * A];
int rt[A], tot_;
inline void insert(int &x, int y, int l, int r, int v) {
x = ++tot_;
tr[x] = tr[y];
tr[x].num++;
if (l == r) return;
int mid = (l + r) >> 1;
if (v <= mid)
insert(tr[x].ls, tr[y].ls, l, mid, v);
else
insert(tr[x].rs, tr[y].rs, mid + 1, r, v);
return;
}
inline int Kth(int x, int y, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int num = tr[tr[y].rs].num - tr[tr[x].rs].num;
if (k <= num)
return Kth(tr[x].rs, tr[y].rs, mid + 1, r, k);
else
return Kth(tr[x].ls, tr[y].ls, l, mid, k - num);
}
inline void DFS(int x) {
pos[x] = ++tot, idx[pos[x]] = x;
for (int i = 1; i <= lg[dep[x]]; i++) f[x][i] = f[f[x][i - 1]][i - 1];
for (int y = head[x]; y; y = road[y].nex) {
int z = road[y].to;
dep[z] = dep[x] + 1;
f[z][0] = x;
DFS(z);
sz[x] += sz[z];
}
if (!sz[x]) sz[x] = 1;
ed[x] = tot;
return;
}
inline int qurey(int x, int v, int k) {
for (int i = lg[dep[x]]; ~i; i--)
if (val[f[x][i]] <= v) x = f[x][i];//倍增时val[0]=1e9就有可能跳到0了
if (sz[x] < k) return -1;
return Kth(rt[pos[x] - 1], rt[ed[x]], 0, INF, k);
}
inline void work() {
lg[1] = 0;
for (int i = 2; i <= all; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 0; i < root.size(); i++) {
dep[root[i]] = 1;
DFS(root[i]);
}
for (int i = 1; i <= tot; i++) {
rt[i] = rt[i - 1];
if (hi[idx[i]]) insert(rt[i], rt[i - 1], 0, INF, hi[idx[i]]);
}
while (Q--) {
int x = in(), v = in(), k = in();
out(qurey(x, v, k)), pc('\n');
}
return;
}
} // namespace Tree
namespace T {
struct Road {
int x, y, w;
inline friend bool operator<(Road u, Road v) { return u.w < v.w; }
} p[A];
int f[A];
inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
inline void work() {
n = in(), m = in(), Q = in();
for (int i = 1; i <= n; i++) hi[i] = in();
for (int i = 1; i <= m; i++) p[i].x = in(), p[i].y = in(), p[i].w = in();
sort(p + 1, p + 1 + m);
for (int i = 1; i <= (n << 1); i++) f[i] = i;
all = n;
for (int i = 1; i <= m; i++) {
int x = p[i].x, y = p[i].y;
if (find(x) == find(y)) continue;
val[++all] = p[i].w;
Tree::edge(all, find(x)), Tree::edge(all, find(y));
f[find(x)] = f[find(y)] = all;
}
val[0] = INF;
for (int i = 1; i <= n; i++)
if (!ex[find(i)]) {
root.pb(find(i));
ex[find(i)] = 1;
}
return;
}
} // namespace T
signed main() {
T::work();
Tree::work();
flush();
return 0;
}
```
by ghr_226 @ 2020-09-17 21:13:18
二格缩进邪教
by Cutest_Junior @ 2020-09-17 21:14:58
@[Cutest_Junior](/user/246014) 似乎确凿是邪教。
by wolf_moon @ 2021-07-21 23:05:31
十分感谢
by 5_Lei @ 2023-02-15 09:47:14
致谢!(`・ω・´)ゞ(`・ω・´)ゞ
by 政凯 @ 2023-05-25 19:50:30
@[ghr_226](/user/225048) 我靠,挂的一模一样!感谢楼主!
by Forever1507 @ 2023-07-10 20:46:27
感谢!
by __ycx2010__ @ 2023-10-06 16:50:20