这道题珂以用启发式合并+主席树来做
离线做法就不行了
我们就要用一个叫做kruscal重构树的东西来解决这个问题
克鲁斯卡尔重构树可以用来解决一类诸如“查询从某个点出发经过边权不超过val的边所能到达的节点”的问题
首先不难发现，上面这个问题肯定是在最小生成树上走最优，其他边都可以不用去管
kruscal构树的思想就是在建最小生成树的时候不是直接连边，而是新建一个节点，并把这个节点的值设为边权，然后令两个连通块的代表点分别作为它的左右儿子。然后令这个新节点成为整个连通块的代表点
那么这样做有什么用呢？
kruscal重构树有这样的性质：一个点的所有子树节点的权值都小于等于它的权值，并且从它开始逐渐向子节点移动，权值是单调不上升的。这个性质是显然的，因为我们在构造树的时候是从小到大插入的边，因此父亲节点的权值一定大于等于子节点的值
查询时，首先可以在树上倍增得到当前查询点所能够到达的最远的祖先点，那么从这个点能够到达的符合边权限制条件的连通块中的节点，就是祖先点的子树中所有的叶节点
然后我们按dfs序维护一个主席树上树就可以解决了
完整代码（离线）
#include <bits/stdc++.h>
#define getchar nc
#define N 200005
#define M N<<4
#define K 500005
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
struct node{
int u,v,c;
node(){}
node(int u,int v,int c):u(u),v(v),c(c){}
inline bool operator <(const node &b)const
{
return c<b.c;
}
}E[K];
struct edge{
int to,next;
}e[N];
int head[N],tot;
inline void add(register int u,register int v)
{
e[++tot]=(edge){v,head[u]};
head[u]=tot;
}
int n,m,q,limit,dfn;
int bin[25];
int fa[N],val[N],f[N][20];
int b[N>>1],h[N>>1];
int ls[N],rs[N],rt[N],num;
int sum[M],L[M],R[M],cnt;
inline void mission(register int x)
{
for(register int i=1;bin[i]<=n;++i)
f[x][i]=f[f[x][i-1]][i-1];
}
inline void update(register int last,register int &now,register int l,register int r,register int x)
{
sum[now=++cnt]=sum[last]+1;
if(l==r)
return;
int mid=l+r>>1;
if(x<=mid)
R[now]=R[last],update(L[last],L[now],l,mid,x);
else
L[now]=L[last],update(R[last],R[now],mid+1,r,x);
}
inline int query(register int a,register int x,register int k)
{
int l=1,r=limit;
for(register int j=18;~j;--j)
if(f[a][j]&&val[f[a][j]]<=x)
a=f[a][j];
int v=rt[rs[a]],u=rt[ls[a]-1];
if(sum[v]-sum[u]<k)
return -1;
while(l<r)
{
int tmp=sum[R[v]]-sum[R[u]],mid=l+r>>1;
if(tmp>=k)
v=R[v],u=R[u],l=mid+1;
else
v=L[v],u=L[u],r=mid,k-=tmp;
}
return b[r];
}
inline void dfs(register int u)
{
mission(u);
ls[u]=++num;
if(u<=n)
update(rt[num-1],rt[num],1,limit,h[u]);
else
rt[num]=rt[num-1];
for(register int i=head[u];i;i=e[i].next)
dfs(e[i].to);
rs[u]=num;
}
inline int find(register int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
n=read(),m=read(),q=read();
bin[1]=1;
for(register int i=2;i<=22;++i)
bin[i]=bin[i-1]<<1;
for(register int i=1;i<=n<<1;++i)
fa[i]=i;
for(register int i=1;i<=n;++i)
b[i]=h[i]=read();
sort(b+1,b+n+1);
limit=unique(b+1,b+n+1)-b-1;
for(register int i=1;i<=n;++i)
h[i]=lower_bound(b+1,b+limit+1,h[i])-b;
for(register int i=1;i<=m;++i)
{
int u=read(),v=read(),c=read();
E[i]=node(u,v,c);
}
sort(E+1,E+m+1);
dfn=n;
for(register int i=1;i<=m;++i)
{
int u=find(E[i].u),v=find(E[i].v);
if(u!=v)
{
val[++dfn]=E[i].c;
fa[u]=fa[v]=dfn;
add(dfn,u),add(dfn,v);
f[u][0]=f[v][0]=dfn;
if(dfn-n==n-1)
break;
}
}
for(register int i=1;i<=dfn;++i)
if(!ls[i])
dfs(find(i));
while(q--)
{
int v=read(),x=read(),k=read();
write(query(v,x,k)),puts("");
}
return 0;
}
完整代码（在线）
#include <bits/stdc++.h>
#define getchar nc
#define N 200005
#define M N<<4
#define K 500005
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
struct node{
int u,v,c;
node(){}
node(int u,int v,int c):u(u),v(v),c(c){}
inline bool operator <(const node &b)const
{
return c<b.c;
}
}E[K];
struct edge{
int to,next;
}e[N];
int head[N],tot;
inline void add(register int u,register int v)
{
e[++tot]=(edge){v,head[u]};
head[u]=tot;
}
int n,m,q,limit,dfn;
int bin[25];
int fa[N],val[N],f[N][20];
int b[N>>1],h[N>>1];
int ls[N],rs[N],rt[N],num;
int sum[M],L[M],R[M],cnt;
inline void mission(register int x)
{
for(register int i=1;bin[i]<=n;++i)
f[x][i]=f[f[x][i-1]][i-1];
}
inline void update(register int last,register int &now,register int l,register int r,register int x)
{
sum[now=++cnt]=sum[last]+1;
if(l==r)
return;
int mid=l+r>>1;
if(x<=mid)
R[now]=R[last],update(L[last],L[now],l,mid,x);
else
L[now]=L[last],update(R[last],R[now],mid+1,r,x);
}
inline int query(register int a,register int x,register int k)
{
int l=1,r=limit;
for(register int j=18;~j;--j)
if(f[a][j]&&val[f[a][j]]<=x)
a=f[a][j];
int v=rt[rs[a]],u=rt[ls[a]-1];
if(sum[v]-sum[u]<k)
return -1;
while(l<r)
{
int tmp=sum[R[v]]-sum[R[u]],mid=l+r>>1;
if(tmp>=k)
v=R[v],u=R[u],l=mid+1;
else
v=L[v],u=L[u],r=mid,k-=tmp;
}
return b[r];
}
inline void dfs(register int u)
{
mission(u);
ls[u]=++num;
if(u<=n)
update(rt[num-1],rt[num],1,limit,h[u]);
else
rt[num]=rt[num-1];
for(register int i=head[u];i;i=e[i].next)
dfs(e[i].to);
rs[u]=num;
}
inline int find(register int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
n=read(),m=read(),q=read();
bin[1]=1;
for(register int i=2;i<=22;++i)
bin[i]=bin[i-1]<<1;
for(register int i=1;i<=n<<1;++i)
fa[i]=i;
for(register int i=1;i<=n;++i)
b[i]=h[i]=read();
sort(b+1,b+n+1);
limit=unique(b+1,b+n+1)-b-1;
for(register int i=1;i<=n;++i)
h[i]=lower_bound(b+1,b+limit+1,h[i])-b;
for(register int i=1;i<=m;++i)
{
int u=read(),v=read(),c=read();
E[i]=node(u,v,c);
}
sort(E+1,E+m+1);
dfn=n;
for(register int i=1;i<=m;++i)
{
int u=find(E[i].u),v=find(E[i].v);
if(u!=v)
{
val[++dfn]=E[i].c;
fa[u]=fa[v]=dfn;
add(dfn,u),add(dfn,v);
f[u][0]=f[v][0]=dfn;
if(dfn-n==n-1)
break;
}
}
for(register int i=1;i<=dfn;++i)
if(!ls[i])
dfs(find(i));
int lastans=0,v,x,k;
while(q--)
{
if(~lastans)
v=read()^lastans,x=read()^lastans,k=read()^lastans;
else
v=read(),x=read(),k=read();
write(lastans=query(v,x,k)),puts("");
}
return 0;
}