设 dp[u][j][0/1] 表示子树内选 j 个点给大头且 u 是否属于大头的最小代价，按 M=2 与 M>=3 分别判断父子边是否计入答案。
OJ: luogu
题目 ID: P4362
难度:提高+/省选-
标签:树形DP动态规划树分类讨论
日期: 2026-06-21 03:56
题意
把树上的 N 个果子分给 M 个头，每个头至少分到一个果子。
其中大头必须吃到恰好 K 个果子，并包含那一个“最大的果子”。
如果一条边两端的果子分给同一个头，这条边也会被一起吃掉，要付出这条边的难受值；如果两端分给不同的头，这条边会被砍断，代价为 0。
要求最小化总难受值。
思路
先看一个可以直接验证题意的暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 60);
const int MAXN = 18;
struct Edge {
int u, v, w;
};
int n, m, k_need;
Edge edges[MAXN];
int color[MAXN];
int choose_big[MAXN];
long long ans;
void brute_two_heads(int u) {
if (u == n + 1) {
int big_cnt = 0;
for (int i = 1; i <= n; i++) {
if (color[i] == 1) {
big_cnt++;
}
}
if (big_cnt != k_need) {
return;
}
long long cost = 0;
for (int i = 1; i < n; i++) {
if (color[edges[i].u] == color[edges[i].v]) {
cost += edges[i].w;
}
}
ans = min(ans, cost);
return;
}
if (u == 1) {
color[u] = 1;
brute_two_heads(u + 1);
return;
}
color[u] = 0;
brute_two_heads(u + 1);
color[u] = 1;
brute_two_heads(u + 1);
color[u] = 0;
}
bool outside_is_bipartite() {
vector<vector<int> > g2(n + 1);
for (int i = 1; i < n; i++) {
int u = edges[i].u;
int v = edges[i].v;
if (!choose_big[u] && !choose_big[v]) {
g2[u].push_back(v);
g2[v].push_back(u);
}
}
vector<int> col(n + 1, -1);
for (int s = 1; s <= n; s++) {
if (choose_big[s] || col[s] != -1) {
continue;
}
queue<int> q;
q.push(s);
col[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (size_t i = 0; i < g2[u].size(); i++) {
int v = g2[u][i];
if (col[v] == -1) {
col[v] = col[u] ^ 1;
q.push(v);
} else if (col[v] == col[u]) {
return false;
}
}
}
}
return true;
}
void brute_many_heads(int u) {
if (u == n + 1) {
int big_cnt = 0;
for (int i = 1; i <= n; i++) {
if (choose_big[i]) {
big_cnt++;
}
}
if (big_cnt != k_need) {
return;
}
if (n - k_need < m - 1) {
return;
}
if (!outside_is_bipartite()) {
return;
}
long long cost = 0;
for (int i = 1; i < n; i++) {
if (choose_big[edges[i].u] && choose_big[edges[i].v]) {
cost += edges[i].w;
}
}
ans = min(ans, cost);
return;
}
if (u == 1) {
choose_big[u] = 1;
brute_many_heads(u + 1);
return;
}
choose_big[u] = 0;
brute_many_heads(u + 1);
choose_big[u] = 1;
brute_many_heads(u + 1);
choose_big[u] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// brute.cpp：直接按题意枚举小数据情况，用来对拍。
cin >> n >> m >> k_need;
for (int i = 1; i < n; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
ans = INF;
if (m == 2) {
memset(color, 0, sizeof(color));
brute_two_heads(1);
} else {
memset(choose_big, 0, sizeof(choose_big));
brute_many_heads(1);
}
cout << ans << '\n';
return 0;
}brute.cpp 直接枚举每个点分给哪个头，然后按照题意计算代价。
它只能处理很小的数据，但很适合对拍。
真正的关键是看清 M=2 和 M>=3 的区别。
当 M=2 时，只有“大头 / 普通头”两种颜色。
所以一条边只要两端分给同一个头，就一定要付这条边的边权。
当 M>=3 时，普通头至少还有两种颜色可用。
而“不属于大头”的那些点组成的是森林，一定可以二染色。
于是普通点之间的边总能安排成两端属于不同普通头，代价为 0。
这时只有“两端都给大头”的边才必须计入答案。
所以做树形 DP：
dp[u][j][0]：u子树里有j个点给大头，且u不给大头的最小代价dp[u][j][1]：u子树里有j个点给大头，且u给大头的最小代价
合并儿子 v 时，只需要根据：
u是否给大头v是否给大头- 当前是
M=2还是M>=3
来决定边 u-v 是否要把边权加进去。
下面这张图展示“同头付代价、异头不付代价”的规则：
graph G {
rankdir=LR;
A [label="u"];
B [label="v"];
A -- B [label="w"];
}
如果两个端点最终被分给同一个头，这条边就会被一起吃掉。 树形 DP 合并子树时，新增加的跨子树边只有父子这一条，所以状态转移可以写得很干净。
DP 转移方程
核心状态：
dp[u][j][0/1]
核心转移：
merge += edge_cost(su,sv,w,M)
答案收束：
min(dp[1][K][0],dp[1][K][1])
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const long long INF = (1LL << 60);
struct Edge {
int to;
int w;
};
int n, m, k_need;
vector<Edge> g[MAXN];
int sz[MAXN];
long long dp[MAXN][MAXN][2];
long long tmp[MAXN][2];
void dfs(int u, int fa) {
sz[u] = 1;
for (int i = 0; i <= k_need; i++) {
dp[u][i][0] = INF;
dp[u][i][1] = INF;
}
// state=0: u 不给大头
// state=1: u 给大头
dp[u][0][0] = 0;
dp[u][1][1] = 0;
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i].to;
int w = g[u][i].w;
if (v == fa) {
continue;
}
dfs(v, u);
int upper = min(k_need, sz[u] + sz[v]);
for (int j = 0; j <= upper; j++) {
tmp[j][0] = INF;
tmp[j][1] = INF;
}
for (int a = 0; a <= min(k_need, sz[u]); a++) {
for (int su = 0; su <= 1; su++) {
if (dp[u][a][su] >= INF) {
continue;
}
for (int b = 0; b <= min(k_need - a, sz[v]); b++) {
for (int sv = 0; sv <= 1; sv++) {
if (dp[v][b][sv] >= INF) {
continue;
}
long long add = 0;
if (m == 2) {
// 两个头时，同色边一定会被吃掉。
if (su == sv) {
add = w;
}
} else {
// 至少三个头时，只要两端都不给大头，就总能用不同普通头把边砍断。
// 因此只有两端都给大头时，这条边才一定要被吃掉。
if (su == 1 && sv == 1) {
add = w;
}
}
long long cand = dp[u][a][su] + dp[v][b][sv] + add;
if (cand < tmp[a + b][su]) {
tmp[a + b][su] = cand;
}
}
}
}
}
sz[u] += sz[v];
if (sz[u] > k_need) {
sz[u] = k_need;
}
for (int j = 0; j <= sz[u]; j++) {
dp[u][j][0] = tmp[j][0];
dp[u][j][1] = tmp[j][1];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k_need;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
cout << dp[1][k_need][1] << '\n';
return 0;
}复杂度
树形 DP 的每次合并是一个背包过程，总复杂度
总结
这题最容易想偏的地方，是误以为“大头吃到的点必须连通”。
题目真正限制的是“边两端同头才付代价”。
看清这一点后，就能把问题转成树上染色 DP。
再进一步利用 M=2 与 M>=3 的差别，就能得到一套统一状态、只改边贡献规则的树形 DP。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
