一棵树一共有2*（n-1)度，现在的任务就是将这些度分配到n个节点，使这n个节点的权值和最大。
思路：因为这是一棵树，所以每个节点的度数都是大于1的，所以事先给每个节点分配一度，答案 ans=f[1]*n
先将答案赋值
所以接下来研究的就是，将剩下的n-2个度分配
即分别看 分配度数为1到n-2的节点的有几个（因为每个节点已经有一度），然后因为每个节点都加上了权值f[1],所以这时f[2]=f[2]-f[1]，以此类推，
看到这里，就是一个完全背包问题：如果还没看出来，详细一点
有1到n-2这些物品，每种物品都有无限个，权值是f[i],现在有一个容量为n-2的背包，去放这些物品，最后使价值最大（就是一个裸的背包问题）
大概就是这样，语言表达能力有限
/*
Problem : 5534 ( Partial Tree ) Judge Status : Accepted
RunId : 15511658 Language : G++ Author : qianbi08
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include <algorithm>
#include<cstring>
using namespace std;
const int INF=-0x3f3f3f3f;
const int maxn=;
int dp[maxn],f[maxn];
int main()
{
int T,n,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;++i)
scanf("%d",&f[i]);
memset(dp,INF,sizeof(dp));
ans=n*f[];
dp[]=;
for(int i=;i<n;++i)
f[i]-=f[];
for(int i=;i<n-;++i)
f[i]=f[i+];
for(int i=;i<=n-;++i)
for(int j=i;j<=n-;++j)
dp[j]=max(dp[j],dp[j-i]+f[i]);
printf("%d\n",ans+dp[n-]);
}
return ;
}