题解 | #牛牛种小树#

一共有n个点，因此度数和为2*(n-1)，首先给每个点分一个度，保证最后形成的是一棵树。

分配n个度后还剩下m=2*(n-1)-n=n-1个度，剩下的这些度的最优分配方案用完全背包的方法dp求得。
背包的体积为m，每个物品的体积和价值分别为i-1（i个度有一个度在之前已经算过了）和w[i]

普通的完全背包不能保证最优选择方案能把背包的体积填满。但该题比较特殊，1~n-1体积的的物品都有，保证最优方案能够把背包填满：当选的物品体积j不足m时，能够在选一个体积为m-j的物品放入背包以增加总价值。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <climits>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 20010, M = 4, INF = 1e9;

LL f[N], w[N];
int n, m;

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i ++)   cin >> w[i];

    m = 2 * (n - 1) - n;
    f[0] = 1ll * n * w[1];  //所有点的度初始化为1，保证没有孤立点
    for (int i = 2; i <= n - 1; i ++)
        for (int j = i - 1; j <= m; j ++)
            f[j] = max(f[j], f[j - i + 1] + w[i] - w[1]);//把一个度数为1的点换成度数为i的点

    cout << f[m];
    return 0;
}