一道很好的树形 dp ！！！！！
树上染色。
错误思路
定义 \(dp[u][i]\) 表示以 \(u\) 为根的子树中，把 \(i\) 个点染成黑色的最大收益。
但这样写，就在转移的时候必须枚举每一个点，复杂度过大，而且还不好写，是十分错误的写法。
正确思路
一般看到有关树上“路径”的题，就要把路径拆成一个个独立的单边，对每个单边独立计算贡献。
我们尝试对某一条边 \((u,v)\) 进行考虑（ \(u\) 为父亲，\(v\) 为儿子）：
设儿子下面有 \(j\) 个黑点，整棵树有 \(k\) 个黑点，树上总共 \(n\) 个点 ，以 \(x\) 为根的子树的点数为 \(sz[x]\) 。
那么经过这条边的路径总数为：儿子下面和父亲上面的黑点的路径数 \((j*(k-j))\) 以及儿子下面和父亲上面的白点的路径数 \(((sz[v]-j)*(n-sz[v]-(k-j)))\) 的和。
然后乘上这条边的长度 \(w_i\) 。
就是这条边的贡献。
于是 dp 状态就出来了：
定义 \(dp[u][i]\) 表示 以 \(u\) 为根的子树中，选 \(i\) 个点作为黑点，对答案整体的最大贡献。
对于转移，我们只需要考虑 \(u\) 与 \(v\) 中的那条边，然后像树形背包一样转移就好了：
细节处理
上界的处理（for(int i=min(k,sz[u]);i>=0;i--)与for(int j=0;j<=min(i,sz[v]);j++)）不必多说，这题的坑点在于下界：
考虑一条链的数据，对于一个点 \(u\) ，其子树的黑色点个数一定是 以 \(u\) 为根的树的黑色点个数 或者 比以 \(u\) 为根的树的黑色点个数少 \(1\) 。
所以如果我们不控制循环的下界，那么在链的 hack 下复杂度将直逼 \(O(n^3)\) 。
这是因为除去该子树，自己父节点下的其他子树的总结点数比 \(i-j\) 小，造成无效转移。
所以解一个不等式：
\[i-j \le sz[u]-sz[v] \]解得
\[j \ge i-sz[u]+sz[v] \]这就是 \(j\) 的下界。
时间复杂度 \(O(n^2)\) 。
树形背包检验自己复杂度正确与否，只需要构造一条链的数据，看看会不会被卡成立方的就好了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,sz[2005];
struct edge{
int to;
ll w;
};
vector<edge>s[2005];
ll dp[2005][2005];
void dfs(int u,int fa)
{
sz[u]=1;
for(auto tmp:s[u])
{
int v=tmp.to;
ll w=tmp.w;
if(v==fa)continue;
dfs(v,u);
sz[u]+=sz[v];
for(int i=min(k,sz[u]);i>=0;i--)
{
for(int j=max(0,i-sz[u]+sz[v]);j<=min(i,sz[v]);j++)
{
dp[u][i]=max(dp[u][i],dp[v][j]+dp[u][i-j]+(1ll*j*(k-j)+1ll*(sz[v]-j)*(n-k-(sz[v]-j)))*w);
}
}
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n-1;i++)
{
int u,v;
ll w;
cin>>u>>v>>w;
s[u].push_back({v,w});
s[v].push_back({u,w});
}
dfs(1,0);
cout<<dp[1][k];
return 0;
}