建出来 $Kruskal$ 重构树.
将询问点向上跳到深度最小，且合法的节点上.
那么，得益于重构树优美的性质，这个最终跳到的点为根的所有子节点都可以与询问点互达.
对于子树中求点权第 $k$ 大的问题，直接对 $dfs$ 序建主席树即可.
#include <cstdio>
#include <algorithm>
#define N 200005
#define M 500002
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
namespace IO {
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}
};
int h[N],rt[N],n,m,Q;
struct Edge {
int u,v,c;
}e[M];
bool cmp(Edge a,Edge b) {
return a.c<b.c;
}
namespace seg {
#define ls t[now].lson
#define rs t[now].rson
struct Node {
int lson,rson,sum;
}t[N*30];
int tot;
void update(int pre,int &now,int l,int r,int p) {
now=++tot;
t[now]=t[pre];
++t[now].sum;
if(l==r) return;
int mid=(l+r)>>1;
if(p<=mid) update(t[pre].lson,ls,l,mid,p);
else update(t[pre].rson,rs,mid+1,r,p);
}
int kth(int rt1,int rt2,int l,int r,int k) {
if(t[rt2].sum-t[rt1].sum==0) return 0;
if(l==r) return l;
int mid=(l+r)>>1,rsize=t[t[rt2].rson].sum-t[t[rt1].rson].sum;
if(k<=rsize) return kth(t[rt1].rson,t[rt2].rson,mid+1,r,k);
else return kth(t[rt1].lson,t[rt2].lson,l,mid,k-rsize);
}
#undef ls
#undef rs
};
namespace tree {
int tot,edges,tim;
int p[N],maxv[N],hd[N],to[N],nex[N],fa[22][N],F[22][N],dfn[N],size[N],dot[N];
void init() {
for(int i=1;i<=n;++i) p[i]=i;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
void addedge(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs(int u,int ff) {
int i,j;
dfn[u]=++tim,dot[tim]=u,size[u]=1;
fa[0][u]=ff, F[0][u]=max(maxv[u],maxv[ff]);
for(i=1;i<=20;++i) {
fa[i][u]=fa[i-1][fa[i-1][u]];
F[i][u]=max(F[i-1][u], F[i-1][fa[i-1][u]]);
}
for(i=hd[u];i;i=nex[i]) dfs(to[i],u),size[u]+=size[to[i]];
}
// 找到最后一个小的等于 k 的点
int get(int x,int k) {
for(int i=20;i>=0;--i)
if(fa[i][x]&&F[i][x]<=k) x=fa[i][x];
return x;
}
void build() {
init();
sort(e+1,e+1+m,cmp);
tot=n;
for(int i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v,c=e[i].c,x,y;
x=find(u),y=find(v);
if(x!=y) {
++tot;
p[x]=p[y]=p[tot]=tot;
maxv[tot]=c;
addedge(tot,x),addedge(tot,y);
}
}
dfs(tot,0);
for(int i=1;i<=tim;++i) {
if(dot[i]>n) rt[i]=rt[i-1];
else seg::update(rt[i-1],rt[i],0,inf,h[dot[i]]);
// printf("%d %d
",i,h[dot[i]]);
}
}
};
int main() {
int i,j;
// setIO("input");
using namespace IO;
n=rd(),m=rd(),Q=rd();
for(i=1;i<=n;++i) h[i]=rd();
for(i=1;i<=m;++i) e[i].u=rd(),e[i].v=rd(),e[i].c=rd();
tree::build();
int lastans=0;
for(i=1;i<=Q;++i) {
int v,x,k;
v=rd(),x=rd(),k=rd();
if(lastans!=-1) {
v^=lastans;
x^=lastans;
k^=lastans;
}
int p=tree::get(v,x);
int l=tree::dfn[p], r=tree::dfn[p]+tree::size[p]-1;
int re=seg::kth(rt[l-1],rt[r],0,inf,k);
printf("%d
",re?re:-1);
lastans=re;
}
return 0;
}