6.30 BZOJ 3551 强制在线，问从一个点v出发只走小于等于x的边能到达的第k大的点。利用kruskal重构树，就是在用克鲁斯卡尔求最小生成树的时候新加一个点向合并的两个点连边，这些虚点的点权就是相连两点的边权，因此具有单调性（由kruskal的过程可以知道这一点，子树中的点权一定小于等于该点），所以我们可以用倍增的方式找一下点权小于等于x的最上方的点。然后搞出这颗树的dfs序，建主席树，从而先倍增然后求区间第k大。从而做到在线。离线的话按权值排序，然后在做克鲁斯卡尔的过程中进行平衡树合并，并完成所有小于等于该边权的所有询问？6.30 BZOJ 3551 强制在线，问从一个点v出发只走小于等于x的边能到达的第k大
阅读背景：
2019 暑期训练 最后一季
来源：互联网
分享到：
