申请添加 hack 数据

错解：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn = 2e3 + 10;
int n, k, sz[maxn], dp[maxn][maxn];
vector<pii> e[maxn];
void cntsz(int u, int fa) {
	sz[u] = 1;
	for (auto [v, w] : e[u]) {
		if (v == fa) continue;
		cntsz(v, u);
		sz[u] += sz[v];
	}
}
void dfs(int u, int fa) {
	dp[u][0] = dp[u][1] = 0;
	for (auto [v, w] : e[u]) {
		if (v == fa) continue;
		dfs(v, u);
		for (int uk = min(sz[u], k); uk >= 0; uk--) {
			for (int vk = 0; vk <= min(sz[v], uk); vk++) {
				int val = w * (vk * (k - vk) + (sz[v] - vk) * ((n - k) - (sz[v] - vk)));
				dp[u][uk] = max(dp[u][uk], dp[u][uk - vk] + dp[v][vk] + val);
			}
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	memset(dp, 0xcf, sizeof dp);
	cin >> n >> k;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	cntsz(1, 0);
	dfs(1, 0);
	cout << dp[1][k];
	return 0;
}

显然复杂度是不严谨的。

随便造一组链就可以卡到 $O(n^3)$。（具体可见洛谷 #12）