1576 . 種樹比賽
Description
序可國舉辦種樹比賽，每一場的比賽都有不同的評分標準，規定大家種出來的樹必須恰好有 N 個點，而且對於每一個點，若它的度數(degree)為 k，則這個點為整棵樹貢獻了 S[k] 的美觀分數。而最終分數就是每一個點所獲得的美觀分數總和，請問最終分數最大可以到多少？
所謂的樹，就是一般的樹，它的邊數一定比點數少一，如下圖所示
以上面的圖當例子，若 S[1]=5, S[2]=1, S[3]=4, S[4]=2, 則這棵樹可以獲得的分數為 4*5+1*1+0*4+1*2=23。
Input Format
輸入的第一行有一個整數 T (1<=T<=300) 表示有幾組測資。
每一筆測試資料的第一列有一個整數 N (2<=N<=50)。第二列有 N-1 個正整數 S[1], S[2], ..., S[N-1]。所有數字的絕對值介於 0 到 10000 之間。
Output Format
對於每一筆測試資料請輸出最終分數可能的最大值。
Sample Input 1
5 4 1 3 0 5 0 0 0 10 7 1 2 3 4 5 6 4 5 0 0 8 1 3 2 5 3 7 5
Sample Output 1
8 10 12 15 20
Hints
Problem Source
Migrated from old NTUJ.
topcoder
Subtasks
| No. | Testdata Range | Score |
|---|