有点权边权的树，选出k个关键点，根必须选。每个点的贡献为点权 * 到最近的关键祖先的距离。求最小总贡献。
解：树形DP是最毒瘤的算法......
设f表示以x为根的子树中选了j个关键点，且x的最近关键祖先是它的i级祖先时的最小贡献。
初态：f = val[x] * dis()，f = 0。
转移：注意到各个i之间是分层转移的，只有女儿i = 0的情况会转移到母亲的每个i。
于是先转移f，再分层转移f。每层是一个树上背包。
#include <bits/stdc++.h> typedef long long LL;
const int N = ; struct Edge {
int nex, v, len;
}edge[N]; int tp; int e[N], n, siz[N], fa[N], val[N], k;
LL f[N][N][N], temp[N][N], d[N]; inline void add(int x, int y, int z) {
tp++;
edge[tp].v = y;
edge[tp].len = z;
edge[tp].nex = e[x];
e[x] = tp;
return;
} inline LL dis(int x, int t) {
int y = x;
for(int i = ; i <= t; i++) {
y = fa[y];
}
return d[x] - d[y];
}
/*
2 1
1 0 2
1 0 3
------------- 2
*/
void DFS(int x) {
//printf("x = %d d[x] = %lld fa[x] = %d \n", x, d[x], fa[x]);
siz[x] = ;
for(int i = ; i <= n; i++) {
f[x][i][] = val[x] * dis(x, i);
//printf("f %d %d %d = %lld = %d * %d\n", x, i, 0, f[x][i][0], val[x], dis(x, i));
}
f[x][][] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
//printf("%d -> %d \n", x, y);
d[y] = d[x] + edge[i].len;
DFS(y);
memcpy(temp, f[x], sizeof(f[x]));
memset(f[x], 0x3f, sizeof(f[x]));
for(int j = ; j <= n; j++) { /// dis
for(int p = ; p <= k; p++) {
for(int r = ; r <= p; r++) {
//printf("r = %d -> %lld \n", r, temp[j][p - r] + f[y][0][r]);
f[x][j][p] = std::min(f[x][j][p], temp[j][p - r] + f[y][][r]); /// don't choose
}
//printf("1f %d %d %d = %lld \n", x, j, p, f[x][j][p]);
}
}
for(int j = ; j <= n; j++) {
for(int p = k; p >= ; p--) {
for(int r = ; r <= p; r++) {
f[x][j][p] = std::min(f[x][j][p], temp[j][p - r] + f[y][j + ][r]); /// choose y
}
//printf("2f %d %d %d = %lld \n", x, j, p, f[x][j][p]);
}
}
siz[x] += siz[y];
}
//printf("%d return \n", x);
return;
} int main() {
memset(f, 0x3f, sizeof(f));
scanf("%d%d", &n, &k);
n++; k++;
k = std::min(k, n);
for(int i = , x, y; i <= n; i++) {
scanf("%d%d%d", &val[i], &x, &y);
add(x + , i, y);
fa[i] = x + ;
} DFS(); printf("%lld\n", f[][][k]);
return ;
}
AC代码
注意每次合并子树的时候，原来的值不能保留。保留下来的要加上f。
恶心死我了...