大意就是把一棵树的点染成m种颜色，其中1号点的颜色必须染恰好k个节点。
总代价是所有两端点颜色相同的边的边权。
求最小代价。
解：可以分为m == 2和m > 2两个题。
m > 2时有代价的边的两端点显然是一号点色的(设为白色)。
m == 2的时候还要计算两端点是另外一种颜色的边的贡献(黑色)。
状态设计就是f[x][j][0/1]表示x为根的子树中染了j个白色点，x号点染/不染的最小代价。
转移的时候做一个类似树上背包的转移即可。
注意m == 2的时候，更新f[i][j][0]合并子树的时候要把原来的那个值覆盖掉，因为子节点也是0的时候会有代价，所以不能保留原来的没有计算这个代价的值。
我比较菜，一开始没发现要分成两个题，就写了两个DFS函数...
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = ; struct Edge {
int nex, v, len;
}edge[N << ]; int top; int f[N][N][], e[N], n, k; inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} void DFS_2(int x, int fa) {
f[x][][] = ;
f[x][][] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS_2(y, x);
for(int j = k; j >= ; j--) {
/// f[x][j] [0/1]
int t = 0x3f3f3f3f;
for(int p = j; p >= ; p--) {
t = std::min(t, std::min(f[y][p][] + f[x][j - p][], f[y][p][] + f[x][j - p][] + edge[i].len));
}
f[x][j][] = t;
t = 0x3f3f3f3f;
for(int p = j; p >= ; p--) {
t = std::min(t, std::min(f[y][p][] + f[x][j - p][] + edge[i].len, f[y][p][] + f[x][j - p][]));
}
f[x][j][] = t;
/*for(int p = j; p >= 0; p--) {
f[x][j][0] = std::min(f[x][j][0], f[y][p][0] + f[x][j - p][0] + edge[i].len);
f[x][j][0] = std::min(f[x][j][0], f[y][p][1] + f[x][j - p][0]);
if(j != p) {
if(x == 1 && j == 2)printf("step 0 f[1][2][1] = %d \n", f[1][2][1]);
f[x][j][1] = std::min(f[x][j][1], f[y][p][0] + f[x][j - p][1]);
if(x == 1 && j == 2)printf("step 1 f[1][2][1] = %d \n", f[1][2][1]);
f[x][j][1] = std::min(f[x][j][1], f[y][p][1] + f[x][j - p][1] + edge[i].len);
if(x == 1 && j == 2)printf("step 2 f[1][2][1] = %d \n", f[1][2][1]);
if(x == 1 && j == 4 && y == 2 && p == 2) {
printf("%d + %d \n", f[y][p][0] + f[x][j - p][1]);
}
if(x == 1 && j == 2) {
printf("> f 1 2 1 = %d p = %d \n", f[1][2][1], p);
printf("> %d + %d \n", f[y][p][0], f[x][j - p][1]);
printf("> %d + %d \n", f[y][p][1], f[x][j - p][1] + edge[i].len);
}
}
}*/
}
}
/*for(int j = 0; j <= k; j++) {
printf("f %d %d %d = %d \n", x, j, 0, f[x][j][0]);
*/
return;
} void DFS_1(int x, int fa) {
f[x][][] = ;
f[x][][] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS_1(y, x);
//
for(int j = k; j >= ; j--) {
/// f[x][j] [0/1]
for(int p = j; p >= ; p--) {
f[x][j][] = std::min(f[x][j][], f[y][p][] + f[x][j - p][]);
f[x][j][] = std::min(f[x][j][], f[y][p][] + f[x][j - p][]);
if(p != j) {
f[x][j][] = std::min(f[x][j][], f[y][p][] + f[x][j - p][]);
f[x][j][] = std::min(f[x][j][], f[y][p][] + f[x][j - p][] + edge[i].len);
}
}
}
}
return;
} int main() {
int m;
memset(f, 0x3f, sizeof(f));
scanf("%d%d%d", &n, &m, &k);
for(int i = , x, y, z; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
if(n - k < m - ) {
puts("-1");
return ;
}
if(m > ) {
DFS_1(, );
printf("%d\n", f[][k][]);
}
else {
DFS_2(, );
printf("%d\n", f[][k][]);
}
return ;
}
AC代码