Problem Description

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two nodes are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

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 nn−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?

 

Input

The first line contains an integer T indicating
the total number of test cases.

Each test case starts with an integer n in
one line,

then one line with n−1 integers f(1),f(2),…,f(n−1).

1≤T≤2015
2≤n≤2015
0≤f(i)≤10000

There are at most 10 test
cases with n>100.

 

Output

For each test case, please output the maximum coolness of the completed tree in one line.

 

Sample Input

 

Sample Output

 

注意到一个节点数为n的树的度数和玮2*n-2,所以问题就转换为了把2*n-2个度分配给n个节点所能获得的最大价值，而且每一个节点至少分到1个度。我们可以先每一个分一个度，然后把n-2个节点任意分配完。分配的时候因为已经分了1个度了，所以要把2~n-1的度看为1~n-1，然后做个完全背包就行了。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 99999999

int v[2200],dp[2200];

int main()

{

    int n,m,i,j,T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(i=1;i<=n-1;i++){

            scanf("%d",&v[i]);

        }

        int ans=0;

        ans+=v[1]*n;

        for(i=2;i<=n-1;i++){

            v[i]-=v[1];

        }

        for(i=1;i<=n-2;i++){

            dp[i]=-inf;

        }

        dp[0]=0;

        for(i=1;i<=n-2;i++){

            v[i]=v[i+1];

        }

        for(i=1;i<=n-2;i++){

            for(j=i;j<=n-2;j++){

                dp[j]=max(dp[j],dp[j-i]+v[i]);

            }

        }

        ans+=dp[n-2];

        printf("%d\n",ans);

    }

}