活动时间：7月7日起至9月1日
活动内容：写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

每日一题交流群，群内定期有福利发放，群号：659028468

今日每日一题预告
【每日一题】7月13日题目预告
题号 NC19810
名称 kingdom
来源 牛客国庆集训派对Day6
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

我们先根据题意一步一步分析，由于只是给出树的节点个数，树可以由我们任意构造，我们假设n个节点取得答案最大的时候树长这样

根节点root，连接着k个子树，k个子树大小分别为sum1,sum2.....sumk，有
(sum1+sum2+..+sumk+1)=n
我们令ans[n]为n个节点的树所得的最优解
root的“心腹”其实就是root的重儿子，我们root的重儿子是所在子树是X，重儿子中全部节点到root的费用，是不是就是ans[sumX]，因为经过重儿子的边到父节点不会有任何影响。如果不是重儿子的所在子树Y（Y不等于X），这个子树的全部节点到root的贡献，是否都需要+1（题意转换，不理解的话仔细读题），因此这个子树的全部点到root的费用，就是ans[sumY]+sumY，sumY个节点，每个都经过边一次。因此，我们可以得出一个结论，
假设重儿子所在子树为X，有
ans[n]=(ans[sum1]+ans[sum2]+...+ans[sumk])+(n−sumX−1)
这里的减1是减去root这个根节点。
这里我们设一个二维数组，dp[i][j]表示 i个节点组成的森林(多个树)，且节点最多的那个树节点数不超过j，注意！！！注意！！！是森林，森林，森林，重要的事情要说三遍！！！！可能不止一棵树，上图

那么现在问题是如何维护ans[]和dp[][]这两个数组？
由上面那幅图我们可以清晰得出，只要枚举n个节点的重儿子所在子树的节点树sumX，
然后可以得到一个可能结果
dp[n−sumX−1][sumX]+n−sumX−1+ans[sumX]
因此，对于ans[n]，只需要枚举sumX不断更新，取最大值，得出公式
ans[n]=dp[n−1−sumX][sumX]+n−1−sumX+ans[sumX]，且1<=sumX<n
现在只剩下dp[][]数组了，我们来看，dp[i][j]，节点总数为i，最大树节点数小于等于j的森林，有以下两种可能：
1.dp[i][j]=dp[i][j−1] ，小于等于j-1必定小于等于j，可以直接更新
2.dp[i][j]=dp[i−x][j]+ans[x] ，x<=j, 由一棵节点数为x的树和一个节点总数为i-x的森林，且这个森林的节点最多的那棵树不超过j 组成 节点总和为i，节点最多的树不超过j的森林
取上面两种情况的最小值即可，由于数据是8000，复杂度不能超过n^2，第一重for循环肯定是枚举节点总数i = 1~n，然后枚举sumX，求得ans[i]，然后更新dp[][],由于dp和ans[x]这一变量有关，类似于完全背包，在枚举的时候会得到一个新的物品ans[i],枚举放入这个背包，背包容量是n，然后更新即可，完结，撒花★,°:.☆(￣▽￣)/$:.°★ 。

感谢@fuzhiji同学提供的题解，奖励牛币100已发放～

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月20日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴