{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 Megamind 的文章《2015年ACM/ICPC长春赛区 H题（01背包）》','https://www.xiaopingtou.net/article-54207.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
题目链接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5202
题意：给你n(n<=2015)个点，定义f(x)为度为x的点的值。然后给你f(1)~f(n-1)。
让你构造一棵树，使所有点的值之和最大。只需要输出这个最大值。
思路：很容易想到，由握手定理，所有点度数之和为2*n-2。由于是树（连通），每个点至少分配1度。
然后剩下的n-2度就可以做一个01背包了。
代码：
题意：给你n(n<=2015)个点，定义f(x)为度为x的点的值。然后给你f(1)~f(n-1)。
让你构造一棵树，使所有点的值之和最大。只需要输出这个最大值。
思路：很容易想到，由握手定理，所有点度数之和为2*n-2。由于是树（连通），每个点至少分配1度。
然后剩下的n-2度就可以做一个01背包了。
代码：
#include
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2040;
int dp[maxn],n,m,k;
int f[maxn];
int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i