题目链接：
Partial Tree
Partial Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3240 Accepted Submission(s): 1590
You find a partial tree on the way home. This tree has $n$ nodes but lacks of $n-1$ edges. You want to complete this tree by adding $n-1$ edges. There must be exactly one path between any two nodes after adding. As you know, there are $n^{n-2}$ ways to complete this tree, and you want to make the completed tree as cool as possible. The coolness of a tree is the sum of coolness of its nodes. The coolness of a node is $f(d)$, where $f$ is a predefined function and $d$ is the degree of this node. What’s the maximum coolness of the completed tree?
Each test case starts with an integer $n$ in one line,
then one line with $n – 1$ integers $f(1), f(2), \ldots, f(n-1)$.
$1 \le T \le 2015$
$2 \le n \le 2015$
$0 \le f(i) \le 10000$
There are at most $10$ test cases with $n > 100$.
2 3 2 1 4 5 1 4
5 19
分析
比赛的时候一时没反应过来，把总节点数和总度数作为两个维度来DP，利索当然的TLE了。现在一想每个节点至少一个度，所以让f(x)的值都减去f(1)的值，然后再视作x-1个度来处理即可。
#include <bits/stdc++.h>
using namespace std;
#define plog if(0)std::cerr
const int MAXN=2020;
int f[MAXN*2];
int w[MAXN];
int solve(){
int n;
cin>>n;
int d=2*(n-1)-n;
for(int i=0;i<n-1;i++) cin>>w[i];
int w1=w[0];
for(int i=1;i<n-1;i++) w[i]-=w1;
memset(f,-0x3f3f3f3f,sizeof(f));
f[0]=0;
for(int i=1;i<n-1;i++){
for(int j=i;j<=d;j++){
f[j]=max(f[j],f[j-i]+w[i]);
}
}
return f[d]+w1*n;
}
int main(){
int T;
cin>>T;
while(T--){
cout<<solve()<<"\n";
}
return 0;
}