将加权树划分为等加权子树

Question

输入:

< li >具有< code>n个节点的有根树； < li >每个节点< code>p具有正整数权重< code > w(p)； < li >一个节点可以有两个以上的子节点。

问题：

• 将树划分为 k 个子树/分区（显然是通过删除 k-1 边缘）;
• 子树权重 W（p） 是根植于节点 p 的子树中所有节点的权重;
• 所有子树的权重应尽可能均匀 - 最小（W（p））和最大值（W（p））之间的差异应尽可能小。

我还没有找到合适的算法。我应该从哪里开始？提示、说明和伪代码。

Answer 1

假设除了删除边以创建子树之外，您不能修改树。

首先要了解，您不能保证通过简单地删除边，您将在任意边界内拥有子树。您可以创建一棵树，当您拆分它们时，无法在目标边界内创建子树。例如：

a(b(c,d,e,f),g)

你不能把它分成两个平衡的部分。最好的方法是将边从a移到b：

a（g）和b（c，d，e，f）

此外，当k时，这个标准有点定义不足

但你可以想出一种方法，以尽可能平衡的方式将树拆分。

实现您的树，使每个节点拥有其所有子节点的计数。您可以非常有效地将其添加到任何树中。（例如，当您添加一个节点时，您必须通过递增计数向上迭代父节点链。删除一个节点，然后从计数中向上迭代）

然后从根开始向下迭代，以广度优先的方式，直到找到一组以最平衡的方式支配子节点的节点。我没有现成的算法，但我认为你可以很容易地找到一个。

我认为当你想划分成k个子树时，你会创建一个k个树根的数组。这些节点中的一个必须始终是当前树的根，然后向下迭代，查找要替换的k-1个候选节点，以改进分区。您将需要某种终止条件，在这种条件下，您不会向下交互到每个叶节点。E、 g.用最大的候选节点细分任何东西都没有意义。