algorithm - 树中每对节点之间的距离

Question

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

Answer 1

如果您希望通过快速预处理能够足够快地回答 distance(u, v) 形式的查询，您可以使用 LCA .有根树中两个顶点的 LCA 或最低共同祖先是一个顶点，它是它们的祖先，并且是它们所有共同祖先中最低的。有一个不是很复杂的算法可以在对数时间内用 n log n 预处理时间找到 LCA(u, v)。如果需要，我可以描述它。

所以，您的问题可能会按以下方式解决。首先，修复树的根。然后进行上述预处理就可以找到LCA。然后，假设 h[v] 是从 v 到根的距离(可以在线性时间内为所有顶点预先计算)然后 distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)]。