切割树中的边以减少所有子树的最大深度

Question

我的问题可能有点不明确，但我想做的是找到一种算法，可以有效地将树（通过切割边缘）分解为一组子树，使得子树之间的最大深度很小。这是问题的一个版本：

问题 1： 给定一棵树和一个数字 n，切割树的 n 边，以便子树的最大深度最小（在切割选择中）。

对于 n=1，通过几次遍历树，我们可以为每个节点存储其深度、高度及其每个子节点的高度。然后，对于每条边（从父级到子级），创建的两个子树的大小将是 (i) 父级的深度 + 其其他子级的最大高度 + 1 和 (ii) 子级的高度。然后为每条边取这两个值的最大值，并选择边中的最小值。

对于n=2，我们可以在每条边停下来得到(i)和(ii)，然后对于较大的一个，运行n=1的情况。我们将能够节省一些工作，因为如果两个子树都大于我们当前的最小值，我们可以跳过它们。然而，这种类型的复发似乎对于较大的 n 来说效果不佳。

问题的另一个版本可能是：

问题 2： 给定一棵树和深度 d，使每个子树的深度小于或等于 d 的最短切割序列是什么？

如果有人知道有关类似问题的算法，我也有兴趣了解它们。这实际上是针对实际用例的，因此我还会考虑一种优化算法，该算法使用良好的启发式方法来选择要进行哪些剪切。任何意见将不胜感激，谢谢。

Answer 1

问题 2 看起来微不足道：

• 求根（入度为0的顶点）
  • 爬树。将 v 设置为当前顶点，将 vd 设置为距根的距离
    • 如果 vd = d 并且 v 不是叶子
      • 切割 v 与其父级之间的边
      • 重新启动两棵新树的算法
  • 停止

Answer 2

对于问题2：

• 使用 BFS 求每个节点的深度。执行此操作时，维护当前节点的路径数组。当深度大于 d 时，使用此数组将当前节点与数组中的节点 d 关联起来（删除此类节点中的弧将导致当前节点位于深度 d）。
• 选择最大深度的任意节点。如果该深度 > d，则将弧切入 BFS 步骤中找到的关联祖先节点 d 步。不考虑从该祖先节点可到达的所有节点。
• 重复上一步，一旦深度 > d 处没有节点则停止。

总运行时间：O(n)。中间步骤是整个算法的摊销线性时间；每次我们点击它时，从考虑中删除的节点数量都是线性的，但每个节点仅被删除一次。

对于问题 1，我们可以使用上面针对问题 2 概述的方法对 d 运行二分搜索。这使得问题 1 的复杂度为 O(n log n)。