题目描述
有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他 的N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
输入格式
第一行包含两个整数 N, K 。接下来 N-1 行每行三个正整数 fr, to, dis ， 表示该树中存在一条长度为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。
输出格式
输出一个正整数，表示收益的最大值。
in：
3 1
1 2 1
1 3 2
out:
3
分析，这是一道树形dp思想的好题，通俗点讲，本题给你一颗加权树，有黑白两种点，求使得相同颜色的点之间的距离和的最大值。因此，我们选择用dp[now][x]来表示在now分支上选择x个黑点对答案的贡献是
多少，对于状态转移，我们可以看出对于最大值的子结构来书就是每一条分支上的权值*黑点和白点的总数
dp[now][x] = max(dp[now][x], dp[now][x-y] + dp[v][y] + var);
var则是在每一次dfs中新产生的贡献
long long var = 1ll * e[i].w * y * (k - y) + 1ll * e[i].w * (size[v] - y) * (n - k - size[v] + y);
有了转移方程，我们还需要特判掉一些特殊情况。比如说我们枚举在当前的子节点的子树中，我们枚举它里面有x个黑点，那么我们需要一个在其他子树中选了共 n - x个黑点的状态，但是如果其他的子树的大小总和还不到 n-x 的话，那么这个状态显然是不合法的，所以我们要去除这种情况。
#include<bits/stdc++.h> #define re register int typedef long long ll; using namespace std; int head[2005<<1],cnt; int n,k; ll dp[2005<<1][2005<<1]; int size[2005<<1]; struct node { int to; int next; int w; } e[2005<<1]; void add(int x,int y,int w) { e[++cnt].to=y; e[cnt].w=w; e[cnt].next=head[x]; head[x]=cnt; } void dfs(int now,int fa) { size[now]=1; dp[now][0]=dp[now][1]=0; for(re i=head[now]; i; i=e[i].next) { int v=e[i].to; if(v==fa) continue;//因为链式向前星加了双向边，防止死循环 else dfs(v,now); size[now]+=size[v]; for(re x=min(k,size[now]); x>=0; x--)//还能提供的黑点数 for(re y=0; y<=min(x,size[v]); y++)//因x限制所以取最小值 { if(dp[now][x-y]==-1)//特判 continue; else { long long var = 1ll * e[i].w * y * (k - y) + 1ll * e[i].w * (size[v] - y) * (n - k - size[v] + y); dp[now][x] = max(dp[now][x], dp[now][x-y] + dp[v][y] + var); } } } } int main() { cin>>n>>k; for(int i=1; i<=n-1; i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } memset(dp,-1,sizeof(dp)); dfs(1,0); cout<<dp[1][k]<<endl; return 0; }