6.30 BZOJ 3551 强制在线，问从一个点v出发只走小于等于x的边能到达的第k大的点。利用kruskal重构树，就是在用克鲁斯卡尔求最小生成树的时候新加一个点向合并的两个点连边，这些虚点的点权就是相连两点的边权，因此具有单调性（由kruskal的过程可以知道这一点，子树中的点权一定小于等于该点），所以我们可以用倍增的方式找一下点权小于等于x的最上方的点。然后搞出这颗树的dfs序，建主席树，从而先倍增然后求区间第k大。从而做到在线。离线的话按权值排序，然后在做克鲁斯卡尔的过程中进行平衡树合并（我只会嘴），并完成所有小于等于该边权的所有询问？
7.1 BZOJ 3732 把NOIP2013火车运输直接反了一下，给一张无向图，问从A到B的路径上最长边最小是多少。由MST的构造方式可知，每条边都是当前可选的最小的，所以做完MST时图是连通的且MST中这些边都是最小的，所以满足了最长边最小这一点（其实我也只是大致意会了QAQ，这种最长最小类型的似乎都是用MST搞啊），然后直接就是求LCA然后倍增的时候顺便维护一下最大值即可。原题要注意不连通的情况，在洛谷可以交。然后当然可以用克鲁斯卡尔重构树做，求的就是LCA处这个点的值。
洛谷 P4768 NOI2018 归程。做完3551做的这个。感觉做过3551看这个题目很容易意识到是个克鲁斯卡尔重构树的题，然后这里多了一维海拔，那么就要思考是要用哪个东西来建树，想了20多分钟，感觉还是应该按照海拔建最大生成树，因为要满足单调性。然后我就错了，以为应该先倍增上去然后和1号点用LCA讨论来怎么搞。其实这里按照海拔建树后边权就不单调什么的了。所以应该用dij预处理出每个点的最短路，然后倍增上去直接找祖先这个点的子树的最小值，求最小值可以一遍dfs也可以用线段树把dfs序搞出来然后维护区间最值（PS训练太少，其实我都在走简单方法）。感觉想清楚后挺简单的但写起来出了不少错误。
原文：https://www.cnblogs.com/intwentieth/p/11111398.html