algorithm - 在有根树中查找一定距离内的节点数

Question

在一棵有根带权树中，如何找到距每个节点一定距离内的节点数？您只需要考虑向下边缘，例如节点从根向下。请记住，每条边都有一个权重。

我可以在 O(N^2) 时间内使用每个节点的 DFS 并跟踪行进的距离来完成此操作，但是 N >= 100000有点慢。我很确定您可以使用 DP 使用未加权的边缘轻松解决它，但是有人知道如何快速解决这个问题吗？ (小于 N^2)

Answer 1

可以通过以下观察改进我之前对O(nlog d) 时间 和 O(n) 空间的回答:

The number of sufficiently-close nodes at a given node v is the sum of the numbers of sufficiently-close nodes of each of its children, less the number of nodes that have just become insufficiently-close.

我们将距离阈值称为 m，并将两个相邻节点 u 和 v 之间的边缘距离称为 d(u, v)。

每个节点都有一个祖先，它是第一个遗漏的祖先

对于每个节点 v，我们将维护一个初始值为 0 的计数 c(v)。

对于任何节点 v，考虑从 v 的父节点到根节点的祖先链。将此链中的第 i 个节点称为 a(v, i)。请注意，在该链中第一个节点的某个数字 i >= 0 中，需要将 v 算作足够接近，而在其他节点中则不需要。如果我们能够快速找到 i，那么我们可以简单地递减 c(a(v, i+1))(使其(可能进一步)低于 0)，这样当 a 的计数(v, i+1) 的 child 在后面的过程中被添加到它，v 被正确地排除在计数之外。如果我们在将节点 v 的所有子节点添加到 c(v) 之前计算出完全准确的计数，则任何此类排除都会正确地“传播”到父节点计数。

棘手的部分是有效地找到 i。调用从v到根s(v, j)的路径上前j >= 0条边的距离之和，调用这些路径长度的所有depth(v)+1的列表，按升序排列, s(v)。我们要做的是对路径长度列表 s(v) 进行二分搜索，寻找大于阈值 m 的第一个条目:这将在 log(d) 时间内找到 i+1。问题是构建 s(v)。我们可以使用从 v 到根的运行总数轻松地构建它——但这将需要每个节点的 O(d) 时间，从而抵消任何时间改进。我们需要一种在恒定时间内从 s(parent(v)) 构造 s(v) 的方法，但问题是当我们从节点 v 递归到它的子节点 u 时，路径长度“以错误的方式”增长:每个path length x需要变成x + d(u, v)，并且需要在开头添加一个新的path length 0。这似乎需要 O(d) 更新，但有一个技巧可以解决这个问题......

快速找到i

解决方案是在每个节点 v 处计算从 v 到根的路径上所有边的总路径长度 t(v)。这很容易在每个节点的恒定时间内完成:t(v) = t(parent(v)) + d(v, parent(v))。然后，我们可以通过在 s(parent(v)) 的开头加上 -t 来形成 s(v)，并且在执行二分查找时，将每个元素 s(v, j) 视为表示 s(v, j) + t (或者等效地，二进制搜索 m - t 而不是 m)。通过让节点 v 的子节点 u 共享 v 的路径长度数组，可以在 O(1) 时间内在开头插入 -t，其中 s(u) 被视为在 s(v) 之前开始一个内存位置。所有路径长度数组都在大小为 d+1 的单个内存缓冲区内“右对齐”——具体来说，深度为 k 的节点的路径长度数组将从缓冲区内的偏移量 d-k 开始，以便为其后代节点预留空间条目。数组共享意味着兄弟节点将覆盖彼此的路径长度，但这不是问题:我们只需要 s(v) 中的值在前序 DFS 中处理 v 和 v 的后代时保持有效。

通过这种方式，我们获得了 O(d) 路径长度在 O(1) 时间内增加的效果。因此，在给定节点找到 i 所需的总时间是 O(1)(构建 s(v))加上 O(log d)(使用修改后的二分查找找到 i)= O(log d)。单个预序 DFS 遍用于查找和递减每个节点的适当祖先的计数；后序 DFS 通过然后将子计数加到父计数中。可以将这两个过程组合成对节点的单一过程，在递归之前和之后执行操作。