以下代码已经 AC，不过我有一种似乎更好的上下界优化，但不能通过，求大佬证伪。

#include <bits/stdc++.h>

struct edge_t
{
	int v;
	int w;
};

struct degree_t
{
	int v;
	int w;
};

int n, k;
std::vector<edge_t> graph[2001];
int64_t dp[2001][2001];
int size[2001];

int init(int u, int parent)
{
	size[u] = 1;
	for (auto &&i : graph[u])
		if (i.v != parent)
			size[u] += init(i.v, u);
	return size[u];
}

void dfs(int u, int parent)
{
	dp[u][0] = dp[u][1] = 0;
	for (auto &&i : graph[u])
	{
		if (i.v == parent)
			continue;
		dfs(i.v, u);
		for (int j = std::min(k, size[u]); j >= 0; j--)		// can it be even stricter?
			for (int m = std::max(0, j - size[u] + size[i.v]); m <= std::min(j, size[i.v]); m++)
			{
				if (dp[u][j - m] == -1)
					continue;
				int64_t total = m * (k - m) + (size[i.v] - m) * (n - size[i.v] - k + m);
				dp[u][j] = std::max(dp[u][j], dp[u][j - m] + dp[i.v][m] + total * i.w);
			}
	}
}

int main()
{
	scanf("%d %d", &n, &k);
	for (int i = 1; i < n; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		graph[u].push_back({v, w});
		graph[v].push_back({u, w});
	}
	init(1, 0);
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= k; j++)
			dp[i][j] = -1;
	dfs(1, 0);
	printf("%ld", dp[1][k]);
	return 0;
}

在 for (int j = std::min(k, size[u]); j >= 0; j--) 这一行中，$j$ 的下界我认为也可以被约束。

用通俗的语言讲，以 $u$ 为根节点子树之外的部分所含的节点数应当不小于不在 $u$ 子树的黑色节点，即：

所以，我把该行代码修改为了 for (int j = std::min(k, size[u]); j >= std::max(0, k - n + size[u]); j--) 并喜提 WA，求大佬帮助我证伪。

注：我尝试不初始化 $dp = -1$，结果依旧

（真的很不理解，明明在处理 $m$ 的下界时用了同样的方法，为什么 $m$ 可以并且一定需要，$j$ 却不可以，这题做的糟心）