题意：给出你n个节点，请添加n-1条边使得它变成一棵树。这个树必须足够“酷”，每个节点的“酷”值的定义为对于一个度数为x的节点，那么它的一个价值为f(x)，求所有节点最大的酷值和。

题解：dp好题。假设我们考虑到每个点还剩多少度这样分配，那么时间复杂度为O(n3)，明显GG，于是我们考虑将每个点预先分配一度，由于总度数是2n-2，那么就剩下n-2度需要分配。于是我们可以将其他度数的f值变成与度数为1的f值的差值。这样只需要考虑n-2个度数的分配，于是转化为完全背包，时间复杂度为O（n2）。（freeloop还是神啊，一听题意就瞬间给出每个点分配一个度的方案，但是最后都纠结于O(n3)的复杂度，完全没想到无意中已经降了一层，真的是非常有意思了）

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=3000;
const int inf=0x3f3f3f3f;
int n, T;
int f[maxn], dp[maxn];
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i=1;i<n;i++)scanf("%d", &f[i]);
        int ans=f[1]*n;
        for(int i=0;i<n-1;i++)f[i]=f[i+1]-ans/n;
        for(int i=0;i<n;i++)dp[i]=-inf;
        dp[0]=0;
        for(int i=1;i<=n-2;i++){    //分配的度数
            for(int j=0;j+i<=n-2;j++){  //上一个状态
                dp[j+i]=max(dp[j+i], dp[j]+f[i]);
            }
        }
        printf("%d\n", ans+dp[n-2]);
    }
    return 0;
}