问题本质上是找到直径<=k的最大子树,并从n中减去它的大小。可以使用DP解决。
一些有用的观察结果:
以节点v为根的树(T(v))的直径为:
1.如果n没有孩子,则为1,
2.如果有一个孩子c,则为max(diameter T(c), height T(c) + 1),
3.如果有多个孩子,为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)
由于我们关心的是最大化树的大小并限制树的直径,因此我们可以将上述情况翻转,以表明每个子树的限制:
1.对于任何以v为根的树,感兴趣的子树最多只有k层。
2.如果n是T(v)中的一个节点,并且距离v不超过k,其最大大小为1。
3.如果n有一个孩子c,则直径<=k的T(n)的最大大小为max size T(c) + 1。
现在是棘手的部分。如果n有多个孩子,我们必须找到分配可用深度给每个孩子所导致的所有可能的树大小。因此,假设我们在深度3,k = 7,我们还有4个深度可以使用。如果我们有三个孩子,我们可以将所有4个分配给第一个孩子,将3个分配给第一个孩子和1个分配给第二个孩子,将2个分配给第一个孩子,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],它给出了使用最多i个子节点,深度最多为j的k-直径限制树的最大大小。递归是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个子节点提供1到j的深度,并将其余可用深度分配给先前的节点。剩余的可用深度是j、我们正在处理的深度或k-m的最小值,因为分配给子节点i+分配给剩余部分的深度不能超过k。将dp的最后一行的值传输到此节点的maxSize表中。如果使用深度受限的DFS运行上述代码,则会按正确顺序计算所有必需的maxSize条目,节点v的答案是v.maxSize(k)。然后,您需要为树中的每个节点执行此操作一次,答案是找到的最大值。
对于说明的混乱,我很抱歉。对我来说很难思考,也很难描述。通过几个简单的示例,应该会更清楚。我没有计算复杂度,但n很小,在Scala中经过了所有测试用例,需要0.5到1秒。