这个题……感觉离线和在线的代码难度差不多(pb_ds不要说话)。
离线的话，就是把所有询问按照w排个序，然后一边Kruskal+平衡树启发式合并一边回答询问就好了。
在线也不难写。首先Kruskal重构树(这个Kruskal重构树是不按秩合并还要添虚点的那种……)，那么每个点可以到达的点一定在某个子树里。子树的dfs序是连续的，所以可以对dfs序建主席树来求区间k大。又因为只有叶子节点的点权是有意义的，所以可以只对叶子的dfs序建主席树。查询的时候倍增跳到最高的w<=询问的w的点然后主席树就好了。
其实树剖跳父亲也可以，先跳整条链，整条链跳不动的时候就在最后一条链上二分，也是O(logn)的。不过可能是太弱，二分写挂了，结果WA到死……无奈用倍增重写了一遍。
限时20s，结果我跑了19.8s，这速度真是感人肺腑……
还有，copy的那个a一开始忘了+1了，调了一节课，虚死……
/**************************************************************
Problem: 3551
User: hzoier
Language: C++
Result: Accepted
Time:19800 ms
Memory:114432 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxe=;
struct edge{
int from,to,w;
bool operator<(const edge &e)const{return w<e.w;}
}e[maxe+maxn];
void Kruskal();
int findroot(int);
void mergeset(int,int);
void dfs(int);
void build(int,int,int&,int);
void query(int,int,int,int);
int sm[maxn<<],lc[maxn<<],rc[maxn<<],root[maxn],tree_cnt=;
int n,M=,m,q,h[maxn],a[maxn],cnt,prt[maxn],w[maxn],f[maxn][],ch[maxn][],L[maxn],R[maxn],pr=,x,d,k,ans;
int main(){
scanf("%d%d%d",&n,&m,&q);
while((<<M)<(n<<))M++;
for(int i=;i<=n;i++)scanf("%d",&h[i]);
copy(h+,h+n+,a+);
sort(a+,a+n+);
for(int i=;i<=n;i++)h[i]=lower_bound(a+,a+n+,h[i])-a;
for(int i=;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
for(int i=;i<=n;i++){
e[++m].from=;
e[m].to=i;
e[m].w=~(<<);
}
cnt=n;
Kruskal();
dfs(cnt);
for(int j=;j<=M;j++)for(int i=;i<=cnt;i++)f[i][j]=f[f[i][j-]][j-];
while(q--){
scanf("%d%d%d",&x,&d,&k);
if(ans!=-){x^=ans;d^=ans;k^=ans;}
for(int j=M;j!=-;j--)if(f[x][j]&&w[f[x][j]]<=d)x=f[x][j];
query(,n,root[R[x]],root[L[x]-]);
printf("%d\n",ans);
}
return ;
}
void Kruskal(){
for(int i=;i<=n;i++)prt[i]=i;
stable_sort(e+,e+m+);
for(int i=;i<=m;i++)if(findroot(e[i].from)!=findroot(e[i].to)){
cnt++;
prt[cnt]=cnt;
w[cnt]=e[i].w;
ch[cnt][]=findroot(e[i].from);
ch[cnt][]=findroot(e[i].to);
mergeset(e[i].from,cnt);
mergeset(e[i].to,cnt);
}
}
int findroot(int x){return prt[x]==x?x:(prt[x]=findroot(prt[x]));}
void mergeset(int x,int y){prt[findroot(x)]=findroot(y);}
void dfs(int x){
if(ch[x][]){
f[ch[x][]][]=f[ch[x][]][]=x;
dfs(ch[x][]);
dfs(ch[x][]);
L[x]=L[ch[x][]];
R[x]=R[ch[x][]];
}
else{
k=h[x];
build(,n,root[pr+],root[pr]);
L[x]=R[x]=++pr;
}
}
void build(int l,int r,int &rt,int pr){
sm[rt=++tree_cnt]=sm[pr]+;
if(l==r)return;
lc[rt]=lc[pr];rc[rt]=rc[pr];
int mid=(l+r)>>;
if(k<=mid)build(l,mid,lc[rt],lc[pr]);
else build(mid+,r,rc[rt],rc[pr]);
}
void query(int l,int r,int rt,int pr){
if(sm[rt]-sm[pr]<k){
ans=-;
return;
}
if(l==r){
ans=a[l];
return;
}
int mid=(l+r)>>;
if(k<=sm[rc[rt]]-sm[rc[pr]])query(mid+,r,rc[rt],rc[pr]);
else{
k-=sm[rc[rt]]-sm[rc[pr]];
query(l,mid,lc[rt],lc[pr]);
}
}
尽头和开端，总有一个在等你。