3

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

问题是这样的：

给你一棵树，它有 N 个顶点和 N-1 条边。您的任务是标记尽可能少的顶点，以使两个未标记顶点之间的最大距离小于或等于 K。您应该将此值写入输出。两个顶点 i 和 j 之间的距离定义为从顶点 j 到达顶点 i 必须经过的最小边数。

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

有没有人可以帮助我？

谢谢。

4

2 回答 2

3

该问题主要包括找到直径 <= k 的最大子树，然后从 n 中减去它的大小。您可以使用 DP 解决它。

一些有用的观察：

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

  • 1 如果 n 没有孩子，
  • max(diameter T(c), height T(c) + 1) 如果有一个孩子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) 中的一个节点，并且没有离 v <= k 的子节点，则它的最大大小为 1。
  • 如果 n 有一个子 c，则直径 <= k 的 T(n) 的最大尺寸为最大尺寸 T(c) + 1。

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

我们想要为每个节点计算 maxSize(d)，它给出了以该节点为根的树的最大大小，深度为 d，直径 <= k。如上所述，具有 0 和 1 个子节点的节点很容易计算（例如，对于一个子节点，v.maxSize(i) = c.maxSize(i - 1) + 1, v.maxSize(0) = 1） . 具有 2 个或更多子节点的节点，您计算 dp[i][j]，它给出了一个 k-diameter-bound 树的最大大小，其中第 i 个子节点占用了 j 个深度。对于从 1 到 j 的 m，递归是 dp[i][j] = max(child(i).maxSize(m - 1) + dp[i - 1][min(j, k - m)]。d[ i][0] = 1。这就是说，尝试给第 i 个孩子 1 到 j 深度，并将剩余的可用深度给前面的节点。“剩余可用深度”是 j 的最小值，深度我们正在使用，或 k - m，因为给孩子 i 的深度 + 给其余孩子的深度不能超过 k。将 dp 的最后一行的值传输到该节点的 maxSize 表。如果您使用深度受限的 DFS 运行上述程序，它将以正确的顺序计算所有必要的 maxSize 条目，节点 v 的答案是 v.maxSize(k)。然后对树中的每个节点执行一次，答案是找到的最大值。

很抱歉解释的混乱性质。我很难思考，也很难描述。通过几个简单的例子应该会更清楚。我没有计算复杂度，但 n 很小，它在 Scala 中以 0.5 到 1 秒的时间完成了所有测试用例。

于 2013-03-06T06:11:16.990 回答
2

我可以注意到一些基本的事情（对其他人来说可能非常明显）： 1. 两个给定顶点之间只有一条可能的路线。2. 最远的顶点将是只有一个出边的那个。

现在来解决问题。

  1. 我将从只有一条边的顶点集开始，并称它们为 EDGE[] 计算 EDGE[] 中顶点之间的距离。这将为您提供 (EDGE[i],EDGE[j],distance ) 值对

  2. 对于 EDGE 中距离 > K 的所有顶点对，DO EDGE[i].occur++,EDGE[i].distance = MAX(EDGE[i].distance, distance) EDGE[j].occur++,EDGE[ j].distance = MAX(EDGE[j].distance, distance)

  3. 在 EDGE[] 中找到最大（距离）的候选人，用最大（发生）标记

  4. 重复直到所有边顶点对的距离小于或等于 K

于 2013-02-20T07:27:09.190 回答