kingdom------(dp)

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

根节点root，连接着k个子树，k个子树大小分别为sum1,sum2.....sumk，有

我们令ans[n]为n个节点的树所得的最优解
root的“心腹”其实就是root的重儿子，我们root的重儿子是所在子树是X，重儿子中全部节点到root的费用，是不是就是ans[sumX]，因为经过重儿子的边到父节点不会有任何影响。如果不是重儿子的所在子树Y（Y不等于X），这个子树的全部节点到root的贡献，是否都需要+1（题意转换，不理解的话仔细读题），因此这个子树的全部点到root的费用，就是ans[sumY]+sumY，sumY个节点，每个都经过边一次。因此，我们可以得出一个结论，
假设重儿子所在子树为X，有

这里的减1是减去root这个根节点。
这里我们设一个二维数组，dp[i][j]表示 i个节点组成的森林(多个树)，且节点最多的那个树节点数不超过j，注意！！！注意！！！是森林，森林，森林，重要的事情要说三遍！！！！可能不止一棵树，上图

那么现在问题是如何维护ans[]和dp[][]这两个数组？
由上面那幅图我们可以清晰得出，只要枚举n个节点的重儿子所在子树的节点树sumX，
然后可以得到一个可能结果
因此，对于ans[n]，只需要枚举sumX不断更新，取最大值，得出公式

现在只剩下dp[][]数组了，我们来看，dp[i][j]，节点总数为i，最大树节点数小于等于j的森林，有以下两种可能：
，小于等于j-1必定小于等于j，可以直接更新
，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，然后更新即可，完结，撒花★,°:.☆(￣▽￣)/$:.°★ 。

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pll pair<long long, long long>
#define P pair<int, int>
#define PP pair<P, P>
#define eps 1e-10
#define PI 3.1415926535898
#define It set<node>::iterator
using namespace std;
const int maxn=8e3+10;
int dp[maxn][maxn],ans[maxn];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<i; j++) {
            ans[i]=max(ans[i],ans[j]+dp[i-j-1][j]+i-j-1);
        }
        for (int j=1; j<=n; j++) {
            dp[j][i]=dp[j][i-1];
            if (j>=i) dp[j][i]=max(dp[j][i],dp[j-i][i]+ans[i]);
        }
    }
    printf("%d\n",ans[n]);
    return 0;
}