题目链接： 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背包了。 代码： #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