题目传送门https://www.luogu.com.cn/problem/P3177

解题思路

设  表示以  为根的子树染  个黑点的最大收益值。

设一共有  个节点，要染  个点。

完成 DP 状态的设计后，开始推导转移方程……

对于一个点 ，它下面有一条通向 ，权值为  的边。

我们枚举 ，表示以  为根的子树已经染了  个点；

然后在枚举  表示以  为子树要染  个点；

然后，这条边的贡献会是多少呢？

首先，如果  为根的子树有  个被染的点，那么是不是  以外应该会有  个点，然后两边的点两两组合，得到的贡献是 。

然后，如果  为根的子树有  个被染的点，那么是不是  为根的子树就会有  个白点？对于  以外，应该会有  个白点。同理，两两组合，贡献是：。

（其中  表示  为根的子树的大小）。

于是，我们可以从 1 号点开始 dfs，同时进行 DP。

代码

记得开 long long！

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
vector<pair<int,int> > g[2001];
int size[2001];
int f[2001][2001];void dfs(int x,int fa)
{size[x]=1;for(auto y:g[x]){int to=y.first;int w=y.second;if(to==fa)continue;dfs(to,x);for(int j=min(m,size[x]);j>=0;j--){for(int k=min(m,size[to]);k>=0;k--){if(j+k<=m){int temp;temp=k*(m-k)*w+(size[to]-k)*(n-m-(size[to]-k))*w;f[x][j+k]=max(f[x][j+k],f[x][j]+f[to][k]+temp);}}}size[x]+=size[to];}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;int u,v,w;for(int i=1;i<=n-1;i++){cin>>u>>v>>w;g[u].push_back(make_pair(v,w));g[v].push_back(make_pair(u,w));}dfs(1,0);cout<<f[1][m];return 0;
}