题目链接：
https://www.luogu.org/problemnew/show/P4197
题目：
在Bytemountains有N座山峰，每座山峰有他的高度$h_i$。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走
现在有Q组询问，每组询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
在线做法题解：
一句话题解：kruskal重构树dfs序上建主席树直接查询第k大即可
知识点拓展：
下面讲讲kruskal重构树是干啥的？这是我第一次做kruskal重构树的题目，下面就当是学习笔记了
从这道题来看，显然我们只需要考虑最小生成树上的路径即可
那么所谓kruskal重构树，就是在kruskal的算法过程中搞一波事情。思想就是在建最小生成树的时候不是直接连边，而是新建一个节点，并把这个节点的值设为边权，然后令两个连通块的代表点分别作为它的左右儿子。然后令这个新节点成为整个连通块的代表点
显然这棵树会具备这样的一个性质：从一个节点向他的儿子一路dfs下去，遍历到的点的点权都是单调递减的，因为我们是排序之后不断加边的（父亲肯定比儿子后建立）
那么我们发现原来的每个节点其实就是这棵子树中的叶子节点，要查询节点x出发经过边权不大于val的路径的点，我们就从节点x不断向上直到找到一个最远的祖先的点权刚好小于等于val，这个祖先的子树中的点显然都满足到x的路径上的边都不超过val
怎么找呢？我们可以倍增
这道题中由于我们要查询第k大，也就是我们要对每个节点的子树中的叶子节点维护第k大。显然可以直接转化为dfs序上查询区间第k大，因此我们还需要主席树
据某大佬说，kruskal重构树可以用来解决一系列“查询从某个点出发经过边权不超过val的边所能到达的节点”的问题，可以和其他数据结构（比如主席树）套用来维护更加复杂的询问
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; const int N=1e5+;
const int M=5e5+;
const int NN=N<<;
const int inf=1e9+;
int n,m,q,xys,tim,tot,cnt;
int height[N];
int fa[NN][],value[NN],in[NN],st[NN],ed[NN],head[NN],leaf[NN],pos[NN],root[NN],f[NN];
int lx[NN<<],rx[NN<<],siz[NN<<];
struct E
{
int x,y,w;
}e[M];
struct EDGE
{
int to,nxt;
}edge[NN];
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
bool cmp(E a,E b) {return a.w<b.w;}
void add(int u,int v)
{
edge[++tot]=(EDGE){v,head[u]};
head[u]=tot;
}
int find(int x)
{
if (f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void dfs(int x)
{
pos[++tim]=x;st[x]=tim;
for (int i=;(<<i)<=(n<<);i++) fa[x][i]=fa[fa[x][i-]][i-];
for (int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if (y==fa[x][]) continue;
fa[y][]=x;
dfs(y);
leaf[x]+=leaf[y];
}
if (!leaf[x]) leaf[x]=;
ed[x]=tim;
}
int update(int pre,int l,int r,int x)
{
int o=++cnt;
lx[o]=lx[pre];rx[o]=rx[pre];siz[o]=siz[pre]+;
if (l==r) return o;
int mid=l+r>>;
if (x<=mid) lx[o]=update(lx[pre],l,mid,x);
else rx[o]=update(rx[pre],mid+,r,x);
return o;
}
int kth(int lr,int rr,int l,int r,int k)
{
if (l==r) return l;
int x=siz[rx[rr]]-siz[rx[lr]];
int mid=l+r>>;
if (k<=x) return kth(rx[lr],rx[rr],mid+,r,k);
else return kth(lx[lr],lx[rr],l,mid,k-x);
}
int query(int v,int x,int k)
{
for (int i=;i>=;i--) if (value[fa[v][i]]<=x&&fa[v][i]) v=fa[v][i];
if (leaf[v]<k) return -;
int l=st[v],r=ed[v];
return kth(root[l-],root[r],,inf,k);
}
int main()
{
n=read();m=read();q=read();
for (int i=;i<=n;i++) height[i]=read();
for (int i=;i<=m;i++)
{
e[i].x=read();e[i].y=read();e[i].w=read();
}
sort(e+,e++m,cmp);
xys=n;//原来节点的标号从1-n
for (int i=;i<=n<<;i++) f[i]=i;
for (int i=;i<=m;i++)
{
int fx=find(e[i].x),fy=find(e[i].y);
if (fx!=fy)
{
value[++xys]=e[i].w;
f[fx]=f[fy]=xys;
add(xys,fx);add(xys,fy);in[fx]++;in[fy]++;
}
}
for (int i=;i<=xys;i++) if (!in[i]) dfs(i);
for (int i=;i<=xys;i++)
{
if (pos[i]<=n) root[i]=update(root[i-],,inf,height[pos[i]]);
else root[i]=root[i-];
}
while (q--)
{
int v=read(),x=read(),k=read();
printf("%d\n",query(v,x,k);
}
return ;
}
离线做法题解：
同样我们要在kruskal的算法流程上做文章
考虑把询问按x排序，每次把不大于这个长度的边加入最小生成树，然后对每个联通块建主席树，加边合并主席树。最后再当前查询点所在的主席树中查询第k大即可
这个好想一点
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#define mid ((l+r)>>1)
using namespace std; const int M=5e5+;
const int N=1e5+;
const int inf=1e9;
int n,m,Q,tot;
int rt[N],fa[N],lx[N<<],rx[N<<],siz[N<<],ans[M],hei[N];
struct EDGE
{
int x,y,w;
}e[M];
struct Que
{
int id;
int v,x,k;
}q[M];
bool operator < (EDGE x,EDGE y) {return x.w<y.w;}
bool operator < (Que x,Que y) {return x.x<y.x;}
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''|ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
int find(int x)
{
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void update(int &o,int l,int r,int x)
{
if (!o) o=++tot;
siz[o]++;
if (l==r) return;
if (x<=mid) update(lx[o],l,mid,x);
else update(rx[o],mid+,r,x);
}
void merge(int &x,int y)
{
if (!x||!y) {x=x|y;return;}
siz[x]+=siz[y];
merge(lx[x],lx[y]);
merge(rx[x],rx[y]);
}
int kth(int o,int l,int r,int k)
{
if (l==r) return l;
if (siz[rx[o]]>=k) return kth(rx[o],mid+,r,k);
else return kth(lx[o],l,mid,k-siz[rx[o]]);
}
int main()
{
n=read();m=read();Q=read();
for (int i=;i<=n;i++) fa[i]=i,hei[i]=,update(rt[i],,inf,read());
for (int i=;i<=m;i++)
{
e[i].x=read();e[i].y=read();e[i].w=read();
}
sort(e+,e++m);
for (int i=;i<=Q;i++)
{
q[i].id=i;
q[i].v=read();q[i].x=read();q[i].k=read();
}
sort(q+,q++Q);
int l=,cnt=;
for (int i=;i<=Q;i++)
{
int v=q[i].v,x=q[i].x,k=q[i].k;
while (e[l].w<=x&&l<=m)
{
if (cnt==n-) break;
int f1=find(e[l].x),f2=find(e[l].y);
++l;
if (f1==f2) continue;
++cnt;
if (hei[f1]>hei[f2])//启发式合并
{
merge(rt[f1],rt[f2]);
fa[f2]=f1;
}
else if (hei[f1]<hei[f2])
{
merge(rt[f2],rt[f1]);
fa[f1]=f2;
}
else
{
merge(rt[f1],rt[f2]);
fa[f2]=f1;hei[f1]++;
}
}
v=find(v);
if (siz[rt[v]]<k) ans[q[i].id]=-;else ans[q[i].id]=kth(rt[v],,inf,k);
}
for (int i=;i<=Q;i++) printf("%d\n",ans[i]);
return ;
}