题意

有一颗树，上面有n个结点，每个结点的重儿子到父节点的花费为0，其他花费为1，问这棵树怎么连使得所有的花费之和最大。

解析

如果我们要求深度为4的树，我们可以枚举心腹子树的长度，从1开始枚举到3，然后取其中最大的花费

由此来说

不难想到通过递推来解决这个问题

并且

设为当是花费的最大值，现在考虑递推这个结果

设表示，个点的森林，森林中每棵树大小均不大于，森林中所有点的深度和

若我们已经有了和所有，则这就是一个每种物品数量不限的背包，转移可得

递推时，枚举心腹子树大小，由于其他儿子的子树大小都不能大于,因此递推公式

代码

#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
using namespace std;
const int maxn=8005;
const int MOD=998244353;
int i,j,n,dp[maxn][maxn],f[maxn];
int main(void)
{
    f[1]=0;
    cin>>n;
    for(i=1;i<=n;i++)
        dp[1][i]=i;
    for(i=2;i<=n;i++){
        for(j=1;j<i;j++)f[i]=max(f[i],f[j]+dp[j][i-1-j]);
        for(j=0;j<=n;j++)dp[i][j]=dp[i-1][j];
        for(j=i;j<=n;j++)dp[i][j]=max(dp[i][j],dp[i][j-i]+f[i]+i);
    }
    cout<<f[n]<<endl;
    return 0;
}