问题本质上是找到直径<=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秒。
