Description
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
Input
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。
Output
对于每组询问，输出一个整数表示答案。
Sample Input
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
Sample Output
6
1
-1
8
解题报告：
用时:3h,10RE
这题很思路就是先建立kruskal重构树，然后推断出沿着v跳到深度最小的小于等于限制的点，处，lca以下的子树部分都符合要求，然后就是基本的查询子树内第k大，主席树维护即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=600005,M=300005,S=6550000;
int n,m,Q,a[M],fa[M],cnt=0,head[M],nxt[M<<1],to[M<<1],num=0,l[M][20],totnode=0;
il void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
il int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct edge{int x,y,z;bool operator<(const edge &pr)const{return z<pr.z;}}e[N];
int dfn[M],DFN=0,maxdep,L[M],R[M],ans=0,b[M],tot,root[M];
il void dfs(int x){
int u;
if(x<=n)dfn[++DFN]=x;L[x]=DFN;
for(int i=head[x];i;i=nxt[i]){
u=to[i];l[u][0]=x;
dfs(u);
}
R[x]=DFN;
}
struct node{int l,r,s;}tr[S];
void insert(int &rt,int last,int l,int r,int sa){
rt=++totnode;tr[rt]=tr[last];tr[rt].s++;
if(l==r)return ;
int mid=(l+r)>>1;
if(sa<=mid)insert(tr[rt].l,tr[last].l,l,mid,sa);
else insert(tr[rt].r,tr[last].r,mid+1,r,sa);
}
int lca(int x,int y){
for(int i=maxdep;i>=0;i--)
if(a[l[x][i]]<=y)x=l[x][i];
return x;
}
int query(int rt,int la,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1,sum=tr[tr[rt].l].s-tr[tr[la].l].s;
if(sum>=k)return query(tr[rt].l,tr[la].l,l,mid,k);
return query(tr[rt].r,tr[la].r,mid+1,r,k-sum);
}
void work()
{
int x,y,totedge=0;
scanf("%d%d%d",&n,&m,&Q);
maxdep=16;cnt=n;a[0]=1e9+5;
for(int i=1;i<=n+n;i++)fa[i]=i;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
sort(e+1,e+m+1);sort(b+1,b+n+1);
tot=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=m;i++){
x=find(e[i].x);y=find(e[i].y);
if(x==y)continue;
fa[x]=fa[y]=++cnt;
link(cnt,x);link(cnt,y);
a[cnt]=e[i].z;totedge++;
if(totedge==n-1)break;
}
dfs(cnt);
for(int i=1;i<=n;i++){
a[dfn[i]]=lower_bound(b+1,b+tot+1,a[dfn[i]])-b;
insert(root[i],root[i-1],1,tot,a[dfn[i]]);
}
for(int j=1;j<=maxdep;j++)
for(int i=1;i<=cnt;i++)
l[i][j]=l[l[i][j-1]][j-1];
int k,s,fr,t,sum;
while(Q--){
scanf("%d%d%d",&x,&y,&k);
x^=ans;y^=ans;k^=ans;
s=lca(x,y);
fr=L[s];t=R[s];
sum=tr[root[t]].s-tr[root[fr]].s;
if(sum<k || fr==t)ans=-1;
else ans=query(root[t],root[fr],1,tot,sum-k+1),ans=b[ans];
printf("%d
",ans);
if(ans==-1)ans=0;
}
}
int main()
{
work();
return 0;
}