题解 | #牛牛种小树#

题目大意

给你n个点，f函数的值，现在你要构造一棵树，一个度数为k的点有f(k)点贡献，问你最大贡献

解题思路

对于一棵树，除了根节点每个点都有一个父亲节点，而一个点的度数就是父亲节点数量+子节点数量

那么可以先构造一颗所有点都连向1的数（1为根节点），且先不计算根节点的贡献，那么贡献就是(n-1)*f(1)

注：下文只对深度为2的点进行修改，深度大于2的点的儿子关系已经确定，无需修改,不然会出现重复计算

之后考虑把一些点移到其他点的儿子中，设 $F_i$ 为1的儿子有i个时的最大贡献，那么每次可以以x的代价制造f(x+1)-f(1)点贡献（x<i，将1的x个儿子移到某个点的儿子中，该点度数从1变为了x+1，贡献为f(x+1)-f(1)）

这个过程和背包相似，所以从小到大枚举可以做到每种贡献可以选无限个（完全背包）

最后结果即为 $max_{i=1}^{n-1}F_i\cdot f(i)$ （加上根节点的贡献）

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 10100
using namespace std;
int n;
ll ans,f[N],a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;++i)
        scanf("%lld",&a[i]);
    memset(f,-127/3,sizeof(f));
    f[n-1]=a[1]*(n-1);//初始（n-1）个点度数为1，根节点不算
    for(int i=1;i<n-1;++i)//儿子个数为i
        for(int j=n-1-i;j>0;--j)
            f[j]=max(f[j],f[j+i]+a[i+1]-a[1]);
    for(int i=1;i<=n-1;++i)
        ans=max(ans,f[i]+a[i]);//补上根节点的贡献
    printf("%lld",ans);
    return 0;
}