树中任意两个节点之间的距离

Question

给定一棵树。如何在不使用大小为n * n的二维矩阵的情况下找到每对节点之间的距离。我知道O(n ^ 2)复杂度的解决方案。

- Vineet Setia

---

如果对于每个v1和v2，输出结果为(v1,v2,distance)，那么你无法做得比O(n^2)更好，因为**输出大小本身就是O(n^2)**。请详细说明期望的输出应该是什么。一个简单的例子会很棒。如果针对给定的n个点求解它们两两之间的距离，并且将所有距离小于等于特定值的点对返回，则输出大小为O(n^2)。因此，O(n^2)是最优时间复杂度。期望的输出是一个由所有满足条件的点对组成的列表，其中每个点对表示两个距离小于等于特定值的顶点以及它们之间的距离。例如，当n=3时，如果特定值为2，则可能的输出如下所示：[(1, 2, 1), (1, 3, 2), (2, 3, 1)]。 - amit

这可能很有用树中所有对最短路径。 - sg08

Answer 1

如果你想要快速预处理并回答形如distance(u, v)的查询，可以使用LCA技术。在根据树两个顶点的最近公共祖先（LCA）算法中，LCA是一个顶点，它是它们二者的祖先中最低的一个。有一种不太复杂的算法可以用n log n的预处理时间以对数时间找到LCA(u, v)。如果需要的话我可以描述一下。

因此，您可以通过以下方式解决问题。首先，确定您的树的根。然后进行上述预处理，以便找到LCA。假设h[v]是从v到根的距离（可以为所有顶点在线性时间内预计算），则distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)]。

- Ivan Smirnov

---

请提供链接或使用伪代码解释上述概念。 - Tushar Saha

https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ - Vikram Kumar

这个链接也许会有所帮助：LCA。 - ahmadkarimi12

Answer 2

正如我在评论中提到的，假设您的每一对顶点 v1,v2 在树中的输出应该是 (v1,v2,distance) - 请注意，有 n*(n-1) 这样的顶点对。由于 n*(n-1) 属于 O(n^2) - 而且它是输出的大小，因此不能比 O(n^2) 更好地完成，因此从大 O 表示法的角度来看，您的算法是最优的。

- amit

---

空间复杂度呢？.. 你能在少于O(n^2)的空间复杂度下完成吗？ - Vineet Setia