题目描述
有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。
输入格式
第一行包含两个整数 $n,k$。
第二到 $n$ 行每行三个正整数 $u, v, w$，表示该树中存在一条长度为 $w$ 的边 $(u, v)$。输入保证所有点之间是联通的。
输出格式
输出一个正整数，表示收益的最大值。
样例 #1
样例输入 #1
3 1
1 2 1
1 3 2
样例输出 #1
3
提示
对于 $100\%$ 的数据，$0 \leq n,k \leq 2000$。
题解
计算一条边的贡献： \(val=(cntLeft_{black}\times cntRgiht_{black} + cntLeft_{white}\times cntRgiht_{white}) \times w\) 对于节点 $u$ 而言，边 $(u,v)$ 的贡献受其下方的黑色点的数量影响（白色点由黑色点的数量决定），记 $dp[u][j]$ 表示以 $u$ 为根节点且包含 $j$ 个黑色点的子树中所有边的贡献，状态转移（背包问题）如下： \(dp[u][j] = \max(dp[u][j], dp[u][j-t]+dp[v][t]+val(u,v))\) 由于降维外层循环需要倒序遍历。