题意：有n个结点，n-1条边，现在要把这n个结点连成一棵树，给定了f(i)，表示度为i的结点的价值是f(i)。现在问如何连能够使得Σf(i)的值最大。

思路：每个点至少一个度，所以可分配的度数为n-2，那么剩下就是每种物品可以任意选，转化成背包问题。

#include
#include
#include
#include
#include
#include
#include
#include

int main()
{
int t,n;
int f[],dp[];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%d",&f[i]);
}
clc(dp,);
dp[]=n*f[];
for(int i=;i<=n-;i++)
{
for(int j=i;j<=n-;j++)
{
dp[j]=max(dp[j],dp[j-i]+f[i+]-f[]);//容量为j的背包增加i度后的价值
}
}
printf("%d\n",dp[n-]);
}
return ;
}