【题解】

看了zzq的博客过来也顺便填填坑。

介绍一种树上背包合并的方法：如本题

$f_{i, j}$表示以$i$为根的子树选$j$个，$i$为根的子树内的贡献加上$(i, fa_i)$的贡献的最大值。

转移就很好办啦！

# include <stdio.h>
# include <algorithm>
using namespace std;

typedef long long ll;

int n, k;
ll f[2010][2010], g[20010];
int tot=0, head[200010], next[200010], to[200010], sz[200010], w[200010];
inline void add(int u, int v, int tw) {
	++tot;
	next[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
	w[tot] = tw;
}

inline void dfs(int x, int fa, int v) {
	int siz = 1;
	for (int I=head[x]; I; I=next[I]) {
		if(to[I] == fa) continue;
		dfs(to[I], x, w[I]);
		int newsz = siz + sz[to[I]];
		for (int i=0; i<=newsz && i<=k; ++i) g[i] = 0;
		for (int i=0; i<=siz && i<=k; ++i) {
			for (int j=0; j<=sz[to[I]] && j<=k; ++j) {
				if(i+j>k) continue;
				g[i+j] = max(g[i+j], f[x][i] + f[to[I]][j]);
			}
		}
		for (int i=0; i<=newsz && i<=k; ++i) f[x][i] = g[i];
		siz = newsz;
	}
	sz[x] = siz;
	for (int i=0; i<=siz && i<=k; ++i) {
		if(siz + (k-i) > n) {
			f[x][i] = -666666666;
			continue;
		}
		f[x][i] += (ll)i*(k-i)*v;
		f[x][i] += (ll)(siz-i)*(n-siz-k+i)*v;
 	}
}



int main() {
	scanf("%d%d", &n, &k);
	for (int i=1, u, v, tw; i<n; ++i) {
		scanf("%d%d%d", &u, &v, &tw);
		add(u, v, tw); add(v, u, tw);
	}
	dfs(1, 0, 0);
	printf("%lld\n", f[1][k]);
	return 0;
}