题解 | #牛牛吃米粒#

我们可以轻松地发现这道题是一道dp的题目

对于整张图来说，总共有2*n-2地度数，由于每一个点都至少有一个度数，我们就只剩下n-2的度数可以进行自由分配

我们将每个点看做一个点加上一条没有连上其他点的边，然后在更新的时候将所有点联向当前树的叶子节点上，然后根据其度数做一下背包就好了

f[i] 表示树上已经有i 个点的最佳权值

假设度数为i的贡献为a[i]，当一个节点插入的时候，会损失a[1]的价值，增加a[i-j+1]的价值，所以转移方程为

f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i;

然后直接转移即可

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define LL long long
const int MAXN=1e4+7;
const LL INF=1e18;
LL f[MAXN];
int a[MAXN];
int main()
{


    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0x80,sizeof f);
        int cnt=0;
        int x=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",a+i);
        }
        f[0]=0;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=i;j<=n-2;j++)
            {
                f[j]=std::max(f[j],f[j-i]+1ll*a[i+1]-a[1]);
            }
        }
        LL ans=f[n-2]+1ll*n*a[1];
        std::cout<<ans<<std::endl;

    }

    return 0;
}