kruskal重构树本质就是给并查集显式建树来替代可持久化并查集。将边按困难度从小到大排序后建出该树，按dfs序建主席树即可。查询时跳到深度最浅的满足在该重要度下已被合并的点，在子树内查询第k大。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 200010#define M 500010int n,m,q,a[N],root[N],value[N],fa[N],p[N],size[N],dfn[N],id[N],f[N][19],lastans,tot,cnt=0,t=0;struct data{ int x,y,z; bool operator <(const data&a) const { return z
           
            >1; if (x<=mid) ins(tree[k].l,l,mid,x); else ins(tree[k].r,mid+1,r,x);}int query(int x,int y,int l,int r,int p){ if (!y) return -1; if (l==r) return p<=tree[y].x-tree[x].x?l:-1; int mid=l+r>>1; if (p<=tree[tree[y].r].x-tree[tree[x].r].x) return query(tree[x].r,tree[y].r,mid+1,r,p); else return query(tree[x].l,tree[y].l,l,mid,p-tree[tree[y].r].x+tree[tree[x].r].x);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3551.in","r",stdin); freopen("bzoj3551.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(),q=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].z=read(); sort(e+1,e+m+1); for (int i=1;i<=n*2;i++) fa[i]=i;tot=n; for (int i=1;i<=m;i++) if (find(e[i].x)!=find(e[i].y)) { value[++tot]=e[i].z; addedge(tot,find(e[i].x)),addedge(tot,find(e[i].y)); f[find(e[i].x)][0]=tot,f[find(e[i].y)][0]=tot; fa[find(e[i].x)]=tot,fa[find(e[i].y)]=tot; } for (int i=1;i<=tot;i++) if (!f[i][0]) f[i][0]=i; for (int j=1;j<=18;j++) for (int i=1;i<=tot;i++) f[i][j]=f[f[i][j-1]][j-1]; for (int i=1;i<=tot;i++) if (f[i][0]==i) dfs(i); cnt=0; for (int i=1;i<=tot;i++) { root[i]=root[i-1]; ins(root[i],-1,1E9,dfn[i]>n?-1:a[dfn[i]]); } while (q--) { int x=read(),y=read(),z=read(); if (~lastans) x^=lastans,y^=lastans,z^=lastans; for (int j=18;~j;j--) if (value[f[x][j]]<=y) x=f[x][j]; lastans=query(root[id[x]-1],root[id[x]+size[x]-1],-1,1E9,z); printf("%d\n",lastans); } return 0;}