6

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

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

4

2 回答 2

3

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

给定节点 v 的足够接近节点的数量是其每个子节点的足够接近节点的数量之和，减去刚刚变得不够接近的节点的数量。

让我们称距离阈值 m，以及两个相邻节点 u 和 vd(u, v) 之间的边上的距离。

每个节点都有一个祖先，它是第一个错过的祖先

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

对于任何节点 v，考虑从 v 的父节点到根节点的祖先链。将此链中的第 i 个节点称为 a(v, i)。请注意，在此链中的第一个节点的某个数量 i >= 0 中，需要将 v 计算为足够接近，而在其他节点中则不需要。如果我们能够快速找到 i，那么我们可以简单地将c(a(v, i+1))递减（使其（可能进一步）低于 0），这样当 a(v, i+1) 的计数的孩子在稍后的传递中添加到它， 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 时，路径长度会以“错误的方式”增长：每个路径长度 x 需要变为 x + d(u, v)，并且需要在开头添加一个新的路径长度 0。这似乎需要 O(d) 更新，但有一个技巧可以解决这个问题......

快速找到我

解决方案是在每个节点 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 的节点的路径长度数组将从缓冲区内的偏移量 dk 开始，以便为它们的后代节点留出空间来添加条目。数组共享意味着兄弟节点将覆盖彼此的路径长度，但这不是问题：我们只需要 s(v) 中的值保持有效，同时在前序 DFS 中处理 v 和 v 的后代。

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

于 2012-12-17T13:37:25.147 回答
2

[编辑：请参阅我的其他答案以获得更有效的 O(nlog d) 解决方案:) ]

这是一个简单的 O(nd) 时间、O(n) 空间算法，其中 d 是树中任何节点的最大深度。具有 n 个节点的完整树（每个节点具有相同数量的子节点的树）的深度为 d = O(log n)，因此在大多数情况下，这应该比基于 O(n^2) DFS 的方法快得多在这种情况下，尽管如果每个节点足够接近的后代数量很少（即如果 DFS 仅遍历少量级别），那么您的算法也不应该太糟糕。

对于任何节点 v，考虑从 v 的父节点到根节点的祖先链。请注意，在此链中的第一个节点的某个数量 i >= 0 中，需要将 v 计算为足够接近，而在其他节点中则不需要。所以我们需要做的就是对于每个节点，向上爬向根，直到总路径长度超过阈值距离 m，随着我们去增加每个祖先的计数。 有n个节点，每个节点最多有d个祖先，所以这个算法很简单O(nd)。

于 2012-12-17T11:00:44.633 回答