求助

回复帖子

@世外明月  2020-02-14 19:03 回复

给定一棵n个点的树,将树上 $\frac{n(n-1)}{2}$ 条路径按照长度从大到小排序,求第 $k$ 长的路径的长度。

输入中会给出 $n,k$ ,以及其余 $n-1$ 条边的起点,终点,长度。

输出第 $k$ 长的路径的长度。

其中 边长 $\le 10000$ ,$n\le50000$

然后目前有一个比较粗糙的思路,可能有些帮助:

二分第 $k$ 长路径的长度,然后点分治判断有几条小于等于 $k$ 的路径。但是由于判断小于等于 $k$ 的路径需要 $O(max{路径长})$ 的辅助空间(就是开了一个树状数组),如果是一条链,空间就爆炸了。

dalao有什么方法吗?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。