algorithm - 图中具有特定距离的顶点对

Question

给定一棵有N 个顶点和正数K 的树。找出它们之间的距离为 exactly K 的不同顶点对的数量。请注意，对 (v, u) 和 (u, v) 被认为是同一对 (1 ≤ N ≤ 50000, 1 ≤⟩K ≤ 500).

我无法为此找到最佳解决方案。我可以从每个顶点进行 BFS 并计算从该顶点可到达且距离小于或等于 K 的顶点数。但在最坏的情况下，复杂度将是 2 的数量级。有没有更快的方法？？

Answer 1

您可以通过更简单的方式实现这一点。在树上运行 DFS 并为每个顶点计算与根的距离 - 将它们保存在数组中(通过 o(1) 访问)。

对于图中的每一对顶点:找到他们的 LCA(最低共同祖先在 0(1) 中有算法可以做到这一点)。假设 u 和 v 是 2 个任意顶点，w 是它们的 LCA -> 减去从 w 到根的距离，从 u 到根 - 现在你有 u 和 w 之间的距离。对 v 做同样的事情 -> 使用 o(1) 得到 (v,w) 和 (u,w) 的距离 -> 将它们加在一起得到 (v,u) 距离 - 现在你要做的就是与K比较。

最终复杂度为o(n^2)