有这样一个问题，给定一棵 N （2 ≤ N ≤ 150000）个节点的树，有 N - 1 条边，每边的长度为 L （1 ≤ L ≤ 1000000）对于每个节点 u，找出与 u 距离第 K 远的节点，输出这个距离。
有一个常规解法，列举出所有包含节点 u 的路径，遍历这些路径，找到第 K 远的节点，这也不是什么难事，n * n 复杂度。
列举包含所有路径的算法如下：枚举从一个叶子节点到另一个叶子节点的路径，若有 n 个叶子节点，则有 n * (n - 1)/2 条路径，设路径集合为 S，这些路径包含了这棵树中的所有路径（采用反证法，如果存在一条路径 p，没有被 S 包含，则向着叶子节点的方向，延长 p，直到 p 以叶子节点结束，得到新的路径 pp，它包含了 p，而 pp 一定被 S 包含，所以p 一定被 S 包含，所以假设不成立，故，树中任何一条路径一定被 S 包含）。
算法如下：
1.构建 HashMap<节点，距离)> nodeDistance；
2.那么以下标 i 遍历 S
最后
以上就是温柔背包最近收集整理的关于树中第 K 远节点的全部内容，更多相关树中第内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复