读题，只经过困难值小于等于x的路径，容易想到用Kruskal重构树；又要查询第k高的山峰，我们选择用主席树求解。
先做一棵重构树，跑一遍dfs，重构树中每一个非叶子节点对应一段区间，我们开range[x][0/1]数组来履行此职责，表示该节点维护的最左（最右）的叶子节点。每跑到一个叶子节点就把他插入主席树中。然后就是基本操作了，倍增找到我们想要的点，用该点的range来在主席树中查询即可。
按题目的困难值要求，显然重构树是个大根堆，用v数组存困难值。
下面的两个代码，一个是参考代码，注释很详细，一个是自己写的（差别可能不是很大）......
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=2e5+10;
4 const int M=5e5+10;
5 struct Node{
6 int u,v,w;
7 }e[M];
8 struct Edge{
9 int to,nxt;
10 }f[M<<1];
11 int n,m,q,fa[N],h[N][25],v[N],tot,cnt,head[N],rt[N<<5],ls[N<<5],rs[N<<5],a[N],b[N],sz,num,range[N][2],sum[N<<5];
12 int read(){
13 int x=0,ch=getchar();
14 while(ch<'0'||ch>'9') ch=getchar();
15 while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
16 return x;
17 }
18
19 bool cmp(Node a,Node b){
20 return a.w<b.w;//大根堆
21 }
22
23 int find(int x){
24 return fa[x]==x?x:fa[x]=find(fa[x]);
25 }
26
27 void add(int u,int v){
28 f[++cnt].to=v;
29 f[cnt].nxt=head[u];
30 head[u]=cnt;
31 }
32
33 void kruskal(){
34 for(int i=1;i<=2*n;i++) fa[i]=i;
35 sort(e+1,e+1+m,cmp);
36 tot=n;
37 for(int i=1;i<=m;i++){
38 int x=find(e[i].u),y=find(e[i].v);
39 if(x!=y){
40 fa[x]=fa[y]=++tot,v[tot]=e[i].w;
41 add(tot,x),add(tot,y);
42 h[x][0]=h[y][0]=tot;//处理ST
43 }
44 }
45 }
46
47 void build(int &x,int l,int r){//构建主席树的第0版本
48 x=++cnt;
49 if(l==r) return ;
50 int mid=l+r>>1;
51 build(ls[x],l,mid),build(rs[x],mid+1,r);
52 }
53
54 void update(int pre,int &rt,int l,int r,int k){//构建其他版本
55 rt=++cnt;
56 sum[rt]=sum[pre]+1;
57 if(l==r) return ;
58 int mid=l+r>>1;
59 if(k<=mid) rs[rt]=rs[pre],update(ls[pre],ls[rt],l,mid,k);
60 else ls[rt]=ls[pre],update(rs[pre],rs[rt],mid+1,r,k);//先复制，然后继续构建
61 }
62
63 void dfs(int x){
64 for(int i=1;i<=20;i++) h[x][i]=h[h[x][i-1]][i-1];//处理ST
65 range[x][0]=num;//每个非叶子节点所维护的最左叶子节点
66 if(!head[x]){//x是叶子节点
67 int k=lower_bound(b+1,b+sz+1,a[x])-b;
68 range[x][0]=++num;
69 update(rt[num-1],rt[num],1,sz,k);//每找到一个叶子节点，就构建新的主席树版本
70 return ;
71 }
72 for(int i=head[x];i;i=f[i].nxt)
73 dfs(f[i].to);
74 range[x][1]=num;//x子树中的点遍历完了，他维护的最右叶子节点的值就是num
75 }
76
77 int query(int x,int y,int l,int r,int k){
78 if(l==r) return l;//找到答案了
79 int mid=l+r>>1,q=sum[rs[y]]-sum[rs[x]];
80 if(k<=q) return query(rs[x],rs[y],mid+1,r,k);
81 else return query(ls[x],ls[y],l,mid,k-q);//注意题目要求找第k大的
82 }
83
84 int main(){
85 n=read(),m=read(),q=read();
86 for(int i=1;i<=n;i++) a[i]=b[i]=read();
87 sort(b+1,b+n+1);
88 sz=unique(b+1,b+n+1)-b-1;//离散化
89 for(int i=1;i<=m;i++)
90 e[i].u=read(),e[i].v=read(),e[i].w=read();
91 kruskal();//重构树
92 cnt=0;
93 build(rt[0],1,sz);
94 dfs(tot);//从重构树的根开始遍历
95 while(q--){//处理每次询问
96 int x=read(),y=read(),z=read();
97 for(int i=20;i>=0;i--)//倍增
98 if(h[x][i]&&v[h[x][i]]<=y) x=h[x][i];
99 if(range[x][1]-range[x][0]<z) cout<<-1<<endl;//无解
100 else cout<<b[query(rt[range[x][0]],rt[range[x][1]],1,sz,z)]<<endl;
101 }
102 return 0;
103 }
自己写的丑代码......
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=2e5+10;
4 const int M=5e5+10;
5 struct node{
6 int u,v,w;
7 bool operator<(const node &b) const{return w<b.w;}
8 }e[M];
9 struct edge{
10 int to,nex;
11 }tmp[M<<1];
12 int n,m,q,fa[N],h[N][25],v[N],cnt,tot,num,res,head[N],rt[N<<5],ls[N<<5],rs[N<<5];
13 int a[N],b[N],sz,range[N][2],sum[N<<5];
14 inline int read(){
15 int x=0;char ch=getchar();
16 while(ch<'0'||ch>'9') ch=getchar();
17 while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
18 return x;
19 }
20
21 inline void add(int x,int y){
22 tmp[++tot].nex=head[x];
23 head[x]=tot;
24 tmp[tot].to=y;
25 }
26
27 inline int find(int x){
28 return x==fa[x]?x:fa[x]=find(fa[x]);
29 }
30
31 inline void kruskal(){
32 sort(e+1,e+m+1);
33 cnt=n;
34 for(int i=1;i<=(n<<1);i++) fa[i]=i;
35 for(int i=1;i<=m;i++){
36 int fu=find(e[i].u),fv=find(e[i].v);
37 if(fu!=fv){
38 fa[fu]=fa[fv]=++cnt;
39 v[cnt]=e[i].w;
40 add(cnt,fu),add(cnt,fv);
41 h[fu][0]=h[fv][0]=cnt;
42 }
43 }
44 }
45
46 inline void build(int &x,int l,int r){
47 x=++num;
48 if(l==r) return ;
49 int mid=l+r>>1;
50 build(ls[x],l,mid),build(rs[x],mid+1,r);
51 }
52
53 inline void update(int x,int &y,int l,int r,int k){
54 y=++num;
55 sum[y]=sum[x]+1;
56 if(l==r) return ;
57 int mid=l+r>>1;
58 if(k<=mid) rs[y]=rs[x],update(ls[x],ls[y],l,mid,k);
59 else ls[y]=ls[x],update(rs[x],rs[y],mid+1,r,k);
60 }
61
62 inline void dfs(int x){
63 for(int i=1;i<=20;i++) h[x][i]=h[h[x][i-1]][i-1];
64 range[x][0]=res;
65 if(!head[x]){
66 int k=lower_bound(b+1,b+sz+1,a[x])-b;
67 range[x][0]=++res;
68 update(rt[res-1],rt[res],1,sz,k);
69 return ;
70 }
71 for(int i=head[x];i;i=tmp[i].nex)
72 dfs(tmp[i].to);
73 range[x][1]=res;
74 }
75
76 inline int query(int x/*左边*/,int y/*右边*/,int l,int r,int k){
77 if(l==r) return l;
78 int mid=l+r>>1;
79 int s=sum[rs[y]]-sum[rs[x]];
80 if(k<=s) return query(rs[x],rs[y],mid+1,r,k);
81 else return query(ls[x],ls[y],l,mid,k-s);
82 }
83
84 int main(){
85 n=read(),m=read(),q=read();
86 for(int i=1;i<=n;i++) a[i]=b[i]=read();
87 sort(b+1,b+n+1);
88 sz=unique(b+1,b+n+1)-b-1;
89 for(int i=1;i<=m;i++){
90 e[i].u=read(),e[i].v=read(),e[i].w=read();
91 }
92 kruskal();
93 build(rt[0],1,sz);
94 dfs(cnt);
95 while(q--){
96 int x=read(),y=read(),z=read();
97 for(int i=20;i>=0;i--){
98 if(h[x][i]&&v[h[x][i]]<=y) x=h[x][i];
99 }
100 if(range[x][1]-range[x][0]<z) cout<<-1<<endl;
101 else cout<<b[query(rt[range[x][0]],rt[range[x][1]],1,sz,z)]<<endl;
102 }
103 return 0;
104 }
重构树的节点原来还可以维护区间的左右端点啊（垃圾的我才知道）......
