[HAOI2015] 树上染色
思路：
先考虑怎么计算答案，后动态规划。
数学部分：
我们发现此题让我们计算最大收益，那我们考虑一种染色方案的收益是怎么算出来的：
显然总收益为所有边贡献之和，一条边对收益的贡献显然是经过它的次数与它的权值之积，那么总收益就是 \sum (w[i] \times time[i])。
接下来考虑计算一条边经过次数：
我们设这一条边的两个端点分别为 u，v，用 size[i] 表示以 i 为根的子树的大小，black[i] 表示以 i 为根的子树的黑色点个数，white[i] 表示以 i 为根的子树的白色点个数，那么有：
且恒有 $size[x]=white[x]+black[x]$。
#### 动态规划：
用 $f[u][i]$ 表示 $u$ 的子树中选 $i$ 个黑色点所获得的最大收益，枚举点 $u$ 的出边，设出边所到的点为 $v$ 那么分别枚举以 $u$ 和 $v$ 为根的子树选多少个黑色的点更新答案即可。
注意这里要由大到小枚举选点数量，因为转移是由小范围到大范围，如果由小到大枚举就会用到之前更新的答案导致重复计算。
动态规划不是本题重点，因此不过多赘述，请结合数学部分以及代码理解。
### 代码：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
ll head[2005], cnt;
ll f[2005][2005], size[2005];
struct node {
ll v, w, ne;
}e[5005];
void add(ll u, ll v, ll w) {
e[++cnt]={v, w, head[u]};
head[u]=cnt;
}
void dfs(ll u, ll fa) {
size[u]=1;
for(int i=head[u], v; i; i=e[i].ne) {
v=e[i].v;
if(v==fa) continue;
dfs(v, u);
for(int x=size[u]; x>=0; x--) { //枚举u子树选多少点
for(int y=size[v]; y>=0; y--) { //v子树选多少点
if(x+y>k) continue; //越界跳过
ll time=(y*(k-y))+((size[v]-y)*(n-k-size[v]+y));
/*(y*(k-y))表示black[v]*black[v]*/
/*((size[v]-y)*(n-k-size[v]+y))表示white[v]*white[u]*/
f[u][x+y]=max(f[u][x+y], f[u][x]+f[v][y]+e[i].w*time); //f[u][x+y]由f[u][x]和f[v][y]转移过来，所以要倒序枚举
}
}
size[u]+=size[v];
}
}
int main() {
cin >> n >> k;
for(int i=1; i<n; i++) {
ll u, v, w;
cin >> u >> v >> w;
add(u, v, w), add(v, u, w);
}
dfs(1, 0);
cout << f[1][k];
return 0;
}
```