题意

给出一张图,每次询问询问从点\(v\)开始只经过困难值\(\le x\)的路径所能到达的山峰中第\(k\)高的山峰。

分析

诸如\(\le x\)的路径的问题,我们用Kruskal重构树来解决。

Kruskal重构树以后,结点\(v\)所能够到达的结点就是在结点\(v\)的祖先中找一个权值\(\le x\)的深度最小的结点作为跟结点,显然,这个子树中的所有叶结点就是结点\(v\)所能够到达的结点。

寻找深度最小的祖先满足权值\(\le x\),可以用倍增+二分探查来做。

接下来的问题就是如何获取所有能够到达的结点中第\(k\)高的山峰。

我们把重构以后的树按照dfs序编号以后,对于子树的询问就变成了对于区间的询问,于是问题变成了询问区间第\(k\)大数,主席树的经典题目。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注