申请添加 hack 数据

原题链接：92041.「HAOI2015」树上染色

Grapher

2026-02-04 10:43:43

发布于：浙江

19阅读

0回复

0点赞

错解：

#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）

有帮助，赞一个

去预览

0/2000

全部评论 2

Eucatastrophe‌
要发反馈

2026-02-04 来自浙江
0
- Eucatastrophe‌
  回复
  Eucatastrophe‌
  不过发了AC君也不会理（
  
  2026-02-04 来自浙江
  0
Grapher
其实我已经把洛谷 #12 数据下载下来了

2026-02-04 来自浙江
0
- Grapher
  回复
  Grapher
  $n=k=2000$ ，每一个边权都是 $1$ ，对于每一个 $i(1 \le i \lt n)$ ， $i$ 和 $i+1$ 连边
  
  2026-02-04 来自浙江
  0
- Grapher
  回复
  Grapher
  输出 1333333000
  
  2026-02-04 来自浙江
  0

全部评论 2

热门讨论