题目链接 (Click) (Here)
做法：(Kruskal)重构树上跑主席树
构造方法：把每条边拆出来成一个点，点权是原先的边权。每次连边的时候，连的不再是点，而是其原先点所在的联通块。
(Kruskal)重构树的性质：
-
二叉树
-
如果按最小生成树构造，则自顶到底权值递增（堆）
-
叶节点是原先的树上节点
-
两个在原图中可以经过权值(<=k)的边互相抵达的点，在最小生成树上也可以这样互相抵达，在(Kruskal)重构树上同理。
也就是说，假如一个点不能到比它的权值大的点，那么它能抵达的所有点就在它的子树里面。这个题目里我们从询问点跳到权值(<=x)中权值最大的点，其子树中的叶子节点，就是可以询问点可以通过点权(<=x)的点到达的所有点。
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 500010;
int n, m, q, tot, INF, h[N], fa[N], val[N];
struct edge {int nxt, to;} e[N];
struct _edge {int u, v, w;}_e[M];
bool cmp (_edge lhs, _edge rhs) {
return lhs.w < rhs.w;
}
int find (int x) {
return x == fa[x] ? x : fa[x] = find (fa[x]);
}
int cnt, head[N];
void add_edge (int u, int v) {
e[++cnt] = (edge) {head[u], v}; head[u] = cnt;
}
int rt[N];
#define mid ((l + r) >> 1)
struct Segment_Node {
int sz, ls, rs;
}t[N << 5];
int modify (int _rt, int l, int r, int w) {
int p = ++rt[0];
t[p].sz = t[_rt].sz + 1;
if (l != r) {
if (w <= mid) {
t[p].ls = modify (t[_rt].ls, l, mid, w), t[p].rs = t[_rt].rs;
} else {
t[p].rs = modify (t[_rt].rs, mid + 1, r, w), t[p].ls = t[_rt].ls;
}
} else {
t[p].ls = t[p].rs = 0;
}
return p;
}
int sz[N], id[N], dfn[N], deep[N], fafa[N][20], totsize[N];
int sep[N];
int num (int x) {
return lower_bound (sep + 1, sep + 1 + sep[0], x) - sep;
}
void dfs (int u, int _fa) {
sz[u] = head[u] == 0;
dfn[u] = ++dfn[0];
totsize[u] = 1;
id[dfn[0]] = u;
fafa[u][0] = _fa;
deep[u] = deep[_fa] + 1;
rt[u] = modify (rt[id[dfn[u] - 1]], 1, INF, num (h[u])); //主席树维护高度
for (int i = 1; (1 << i) <= deep[u]; ++i) {
fafa[u][i] = fafa[fafa[u][i - 1]][i - 1];
}
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != _fa) {
dfs (v, u);
sz[u] += sz[v];
totsize[u] += totsize[v];
}
}
}
int query (int u, int v, int l, int r, int k) {
while (l < r) {
int rch = t[t[v].rs].sz - t[t[u].rs].sz;
if (k <= rch) {
u = t[u].rs;
v = t[v].rs;
l = mid + 1;
} else {
u = t[u].ls;
v = t[v].ls;
k -= rch;
r = mid;
}
}
return l;
}
int read () {
int s = 0, w = 1, ch = getchar ();
while ('9' < ch || ch < '0') {
if (ch == '-') w = -1;
ch = getchar ();
}
while ('0' <= ch && ch <= '9') {
s = (s << 1) + (s << 3) + ch - '0';
ch = getchar ();
}
return s * w;
}
int main () {
memset (val, 0x3f, sizeof (val));
tot = n = read (), m = read (), q = read ();
t[0].sz = t[0].ls = t[0].rs = 0, sep[++sep[0]] = 0;
for (int i = 1; i <= n; ++i) sep[++sep[0]] = h[i] = read ();
for (int i = 1; i <= m; ++i) {
_e[i].u = read ();
_e[i].v = read ();
_e[i].w = read ();
}
sort (_e + 1, _e + 1 + m, cmp);
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= m; ++i) {
int u = find (_e[i].u);
int v = find (_e[i].v);
if (u != v) {
int T = ++tot;
val[T] = _e[i].w;
fa[u] = fa[v] = fa[T] = T;
add_edge (T, u);
add_edge (T, v);
}
}
sort (sep + 1, sep + 1 + sep[0]);
INF = sep[0] = unique (sep + 1, sep + 1 + sep[0]) - sep - 1;
dfs (tot, 0);
int lastans = 0;
for (int i = 1; i <= q; ++i) {
int u = read () ^ lastans;
int x = read () ^ lastans;
int k = read () ^ lastans;
for (int j = 19; j >= 0; --j) {
if (val[fafa[u][j]] <= x) {
u = fafa[u][j];
}
}
if (sz[u] < k) {
puts ("-1");
lastans = 0;
} else {
lastans = sep[query (rt[id[dfn[u] - 1]], rt[id[dfn[u] + totsize[u] - 1]], 1, INF, k)];
printf ("%d
", lastans);
}
}
}