algorithm - 找到最大距离不大于 K 的树的最大子集

Question

我在 interviewstreet 上遇到了一个名为“Far Vertices”的动态规划问题。

问题是这样的:

You are given a tree that has N vertices and N-1 edges. Your task is to mark as small number of verices as possible so that the maximum distance between two unmarked vertices be less than or equal to K. You should write this value to the output. Distance between two vertices i and j is defined as the minimum number of edges you have to pass in order to reach vertex i from vertex j.

我试图从树的每个节点进行 dfs，以便找到节点的最大连接子集，以便每对子集的距离不超过 K。但是我无法定义状态，以及状态之间的转换。

有没有人可以帮助我？

谢谢。

Answer 1

问题本质上包括找到直径 <= k 的最大子树，并从 n 中减去它的大小。您可以使用 DP 解决它。

一些有用的观察:

以节点 v (T(v)) 为根的树的直径为:

• 如果 n 没有 child ，则为 1，
• max(直径T(c), 高度T(c) + 1)如果有一个 child c,
• max(max(diameter T(c)) for all children c of v, max(height T(c1) + height T(c2) + 2) for all children c1, c2 of v, c1 != c2)

由于我们关心最大化树的大小和边界树的直径，我们可以翻转上面的内容以建议对每个子树的限制:

• 对于任何以 v 为根的树，感兴趣的子树至多为 k 深。
• 如果 n 是 T(v) 中的一个节点并且没有 <= k 远离 v 的子节点，则其最大大小为 1。
• 如果 n 有一个 child c，则直径 <= k 的 T(n) 的最大尺寸是最大尺寸 T(c) + 1。

现在是棘手的一点。如果 n 有多个 child ，我们必须找到所有可能的树大小，这些树的大小是由为每个 child 分配可用深度而产生的。所以说我们在深度 3，k = 7，我们还有 4 个深度可以玩。如果我们有三个 child ，我们可以将所有 4 个分配给 child 1，将 3 个分配给 child 1，将 1 个分配给 child 2，将 2 个分配给 child 1，将 1 个分配给 child 2 和 3，等等。我们必须小心地做这件事，确保我们没有' 超过直径 k。您可以使用本地 DP 来完成此操作。

我们想要为每个节点计算 maxSize(d)，它给出了以该节点为根的树的最大大小，该树的最大尺寸为 d 深，直径 <= k。具有 0 和 1 个 child 的节点很容易计算出来，如上所述(例如，对于一个 child ，v.maxSize(i) = c.maxSize(i - 1) + 1, v.maxSize(0) = 1) .有 2 个或更多 child 的节点，你计算 dp[i][j]，它给出了一个 k 直径边界树的最大大小，使用最多第 i 个 child 达到 j 深度。递归是 dp[i][j] = max(child(i).maxSize(m - 1) + dp[i - 1][min(j, k - m)] for m from 1 to j. d[ i][0] = 1. 这就是说，尝试给第 i 个 child 1 到 j 深度，并将剩余的可用深度给之前的节点。“可用深度的剩余”是 j 的最小值，即深度我们正在使用，或 k - m，因为给 child i 的深度 + 给其余 child 的深度不能超过 k。将 dp 最后一行的值传输到该节点的 maxSize 表。如果您使用 a 运行上面的深度限制 DFS，它将以正确的顺序计算所有必要的 maxSize 条目，节点 v 的答案是 v.maxSize(k)。然后你对树中的每个节点都这样做一次，答案是最大值发现值(value)。

对于解释的困惑性质，我们深表歉意。我很难想通，也很难描述。通过几个简单的例子应该会更清楚。复杂度我没有计算过，但是n很小，在Scala中用0.5秒到1秒的时间跑完了所有的测试用例。