$\large{思路}$
设 $f_{i,j,k}$ 表示以 $i$ 为根的子树内建 $k$ 个仓库,$i$ 向上走第一个仓库为 $j$ 的最小花费($i$ 点不建立仓库)
设 $g_{i,k}$ 表示以 $i$ 为根的子树内建 $k$ 个仓库的最小花费($i$ 点建立仓库)
于是就可以进行树形 $dp$ 了,转移式见代码。
$\large{code}$
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define re register
#define sz(x) (int(x.size()))
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 110, mod = 1e9 + 7;
int n, k;
int f[N][N][N], g[N][N];
int h[N], e[N], w[N], ne[N], idx;
int stk[N], wood[N], dep[N], tot;
int rd() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - 48; ch = getchar();}
return f * w;
}
void add(int &x, int y) {x = (x + y) % mod;}
void chkmin(int &x, int y) {x = min(x, y);}
void chkmax(int &x, int y) {x = max(x, y);}
void add_edge(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}
void dfs(int u) {
stk[++ tot] = u, g[u][1] = 0;
for (int i = 1; i <= tot; i ++ ) f[u][stk[i]][0] = wood[u] * (dep[u] - dep[stk[i]]);
for (int kk = h[u]; ~kk; kk = ne[kk]) {
int ver = e[kk];
dep[ver] = dep[u] + w[kk];
dfs(ver);
for (int i = 1; i < tot; i ++ )
for (int j = k; j >= 0; j -- ) {
f[u][stk[i]][j] += f[ver][stk[i]][0];
for (int x = 0; x < j; x ++ ) chkmin(f[u][stk[i]][j], f[u][stk[i]][x] + min(f[ver][stk[i]][j - x], g[ver][j - x]));
}
for (int j = k; j >= 0; j -- ) {
g[u][j] += f[ver][u][0];
for (int x = 0; x < j; x ++ ) chkmin(g[u][j], g[u][x] + min(f[ver][u][j - x], g[ver][j - x]));
}
}
tot -- ;
}
int main() {
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
memset(h, -1, sizeof h);
n = rd() + 1, k = rd() + 1;
for (int i = 2; i <= n; i ++ ) {
wood[i] = rd();
int b = rd() + 1, c = rd();
add_edge(b, i, c);
}
dfs(1);
printf("%d\n", g[1][k]);
return 0;
}