给定一棵树，N其中每条边都有权重的顶点1。节点用C颜色着色。对于每种颜色，我们希望找到该颜色的两个节点之间的最大最短距离。
我可以建立一个稀疏表，然后在O(log n). 然后检查所有相同颜色的对。这给了O(n^2 log n). 有可能做得比这更好吗？
问问题
567 次
1 回答
0
您可以正确地处理边缘并从每个节点开始递归遍历，就好像它是根一样。由于树有 N 个节点，N 次遍历会给你O(N 2 )。边的杂耍也应该花费O(n)时间，因为树中有 (n-1) 条边。如果您保留具有 C 行和 C 列的矩阵 M 并在每次遍历时对其进行更新，那么您可以在O(N 2 )整体时间和空间复杂度中做您想做的事情。
基本上，当您在距离 d 处到达颜色为 c v的节点 V 时，您所做的将在从节点 U 开始、颜色为 c u的遍历中更新 M 的第 c行。
M[c u ][c v ] = max(M[c u ][c v ], d)
于 2016-03-26T09:03:20.907 回答