算法
直接bb好像不是很好讲，那就从这道题入手吧。
题目描述
在 Bytemountains 有n座山峰，每座山峰有他的高度 \(h_i\)。有些山峰之间有双向道路相连，共 m 条路径，每条路径有一个困难值，这个值越大表示越难走。
现在有 q 组询问，每组询问询问从点 v 开始只经过困难值小于等于 x 的路径所能到达的山峰中第 k 高的山峰，如果无解输出 -1。
输入格式
第一行三个数 n,m,q。 第二行 n 个数，第 i 个数为 \(h_i\)。
接下来 m 行，每行三个整数 a,b,c表示从 a→b 有一条困难值为 c 的双向路径。 接下来 q 行，每行三个数 v,x,k表示一组询问。
输出格式
对于每组询问，输出一个整数表示能到达的山峰中第 kk 高的山峰的高度。
输入
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
输出
6
1
-1
8
说明/提示
数据规模与约定
对于 100% 的数据，n≤10^5 0≤m,q≤5×10,
h_i, c,x≤10^9
思路
现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出−1
首先，这是一张图(你在说大实话么)
对于一个点来说，经过困难值小于等于x的路径所能到达的点是一定的。
但是这和生成树有啥关系呢？
显然，若一个点能通过一条路径到达，那么我们走最小生成树上的边也一定能到达该节点。
这样我们把最小生成树建出来，就可以少考虑很多边了。
然而并没有什么卵用.
现在我们需要做的，是找一种方法，能够维护出一个点能到达的点。
于是Kruskal重构树就诞生了。
它的思想是这样的：
在运行Kruskal算法的过程中，对于两个可以合并的节点(x,y)，断开其中的连边，并新建一个节点T，把T向(x,y)连边作为他们的父亲，同时把(x,y)之间的边权当做T的点权
比如说
重构之后是这样的：
然后这个点就代表这个点集。
这个题目的样例重构得到的树：
这样我们得到了一个新的树，考虑它有什么性质。
其中最重要的一条就是：一个节点能走到的节点一定在它的子树中
那么我们找到v的点权<=x最远祖先lca。因为祖先节点的点权单增，这个可以倍增搞，那么lca的子树都是v可以得到的节点。
那么就是一个子树的第k大。dfs序建立主席树。主席树只在叶子节点更新。
然后这道题就做完了。O((n+Q)*logn)
当然，除了这一条之外，Kruskal重构树还有很多有意思的性质
1.是一个二叉树
2.如果是按最小生成树建立的话是一个大根堆(important!)
3.任意两个点路径上边权的最大值为它们的LCA的点权
4.一个子树里的节点之间的路径最长边<=根点权
5.树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点。
5.由于新点的创建顺序与原来生成树上边权的大小有关，可以发现，从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的。
6.出于kruskal算法贪心的性质，两个点u和v的lca的点权就对应着它们最小生成树上的瓶颈。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000005;
const int maxm=1000005;
#define mid (l+r>>1)
const int N=2e5+7;
const LL INF=1e18;
struct SegTree {
LL sum[N*40], tot=0;
int L[N*40], R[N*40];
void init () {
for(int i=0; i<=tot; i++){
L[i]=R[i]=sum[i]=0;
}
tot=0;
}
int BT(int l, int r){
int rt=++tot;
sum[rt]=0;
if(l<r){
L[rt]=BT(l, mid);
R[rt]=BT(mid+1, r);
}
return rt;
}
int add(int root, int l ,int r, int x, int val){//a[x]+=val
int rt=++tot;
L[rt]=L[root], R[rt]=R[root], sum[rt]=sum[root]+val;
if(l<r){
if(x<=mid) L[rt]=add(L[root], l, mid, x, val);
else R[rt]=add(R[root], mid+1, r, x, val);
}
return rt;
}
int query(int x, int y, int l, int r, int k){//区间[x, y]的第k小
if(l>=r) return l;//得到答案
int s=sum[R[y]]-sum[R[x]];
if(s>=k) return query(R[x], R[y], mid+1, r, k);
else return query(L[x], L[y], l, mid, k-s);
}
}Tree;
struct Edge{
int from, to, nxt;
}E[maxm];
int head[maxn], cut=0;
int w[maxn];//重构树每个点的点权
int fa[maxn][21];//重构树每个节点父亲
int pos[maxn][2];//树的dfs序
int root[maxn];//根节点
void Addedge(int x, int y){
E[++cut]={x, y, head[x]};
head[x]=cut;
}
int a[maxn];
struct kruskal_Tree{
Edge e[maxm];
int cut=0, T=0;
int f[maxn];
int fd(int x){
if(!f[x]) return x;
return f[x]=fd(f[x]);
}
void add(int x, int y, int w){
e[++cut]={x, y, w};
}
void DFS(int u){
for(int i=1; i<=20; i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
pos[u][0]=T;
//叶子节点
if(!head[u]){
pos[u][0]=++T;
root[T]=Tree.add(root[T-1], 1, N, a[u], 1);
return ;
}
//非叶子节点
for(int i=head[u]; i; i=E[i].nxt){
DFS(E[i].to);
}
pos[u][1]=T;
}
void get_Tree(int n){
sort(e+1, e+cut+1, [](Edge &a, Edge &b){return a.nxt<b.nxt;});
for(int i=1; i<=cut; i++){
int x=fd(e[i].from), y=fd(e[i].to);
if(x==y) continue;
w[++n]=e[i].nxt;
f[x]=f[y]=n;
fa[x][0]=fa[y][0]=n;
Addedge(n, x); Addedge(n, y);//建立重构树
}
//dfs顺序建立主席树
root[0]=Tree.BT(1, N);
DFS(n);
}
}kt;
struct LSH{//离散化
int b[N];
int lsh(int a[], int n){//得到离散化后不同元素的个数
for(int i=1; i<=n; i++) b[i]=a[i];
sort(b+1, b+n+1);
int cnt=unique(b+1, b+n+1)-b-1;
for(int i=1; i<=n; i++){
int x=a[i];
a[i]=lower_bound(b+1, b+cnt+1, a[i])-b;
}
return cnt;
}
int id(int x){//得到原数
return b[x];
}
}Lsh;
int main() {
int n, m, q; scanf("%d%d%d", &n, &m, &q);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
Lsh.lsh(a, n);
for(int i=1; i<=m; i++){
int x, y, w; scanf("%d%d%d", &x, &y, &w);
kt.add(x, y, w);
}
kt.get_Tree(n);
while(q--){
int x, d, k; scanf("%d%d%d", &x, &d, &k);
for(int i=20; i>=0; i--){
if(fa[x][i]&&w[fa[x][i]]<=d) x=fa[x][i];
}
if(pos[x][1]-pos[x][0]<k){//如果x叶子节点小于k,那么没有第k大
printf("-1\n");
continue;
}
printf("%d\n", Lsh.id(Tree.query(root[pos[x][0]], root[pos[x][1]], 1, N, k)));
}
return 0;
}