树形 dp
我们很容易套路地用 \(f_{u,i}\) 表示在 \(u\) 子树中，\(u\) 节点放了 \(i\) 个伐木场的最小花费。但是这样无法转移，原因是无法表示路径长度，也无法知道运送数量。
所以我们现在考虑增加状态，能够表示出距离。只考虑 \(u\) 节点的花费，其木头要运送上去，一定会走一段 \(u\) 到某个祖先的一段距离，如果这个祖先有伐木场，那么距离就是这段长度。于是设 \(f_{u,i,j}\) 表示 \(u\) 子树中放了 \(j\) 个伐木场，在祖先 \(i\) 上有一个伐木场的最小花费。此时因为转移时 \(u\) 子树内的节点已经计算过了，转移完只需要计算 \(u\) 节点的运送花费。
但是仔细一想还是不够，如果 \(u\) 节点有伐木场，那么在转移时 \(v\) 节点的距离就是 \(u\) 到 \(v\)。所以我们还需要加一维表示 \(u\) 建不建伐木场（或者开一个新数组）。
转移时细节的地方：我们在转移时可以先钦定 \(f\) 为 \(u\) 节点不建伐木场，\(g\) 为建伐木场，最后把 \(g\) 合并到 \(f\) 上即可。
复杂度 \(O(n^2k^2)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 110;
int n, k, cnt;
struct node {
int to, nxt, w;
} e[N];
int h[N], w[N];
void add(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
e[cnt].w = w;
h[u] = cnt;
}
int st[N], top;
int f[N][N][N], g[N][N][N], dis[N];
void dfs(int u) {
st[++top] = u;
for(int _ = h[u]; _; _ = e[_].nxt) {
int v = e[_].to;
dis[v] = dis[u] + e[_].w;
dfs(v);
for(int i = 1; i <= top; i++) {
for(int j = k; j >= 0; j--) {
f[u][st[i]][j] += f[v][st[i]][0];
g[u][st[i]][j] += f[v][u][0]; //这里要先转移一次，否则无法正确转移
for(int x = 1; x <= j; x++) {
f[u][st[i]][j] = std::min(f[u][st[i]][j], f[u][st[i]][j - x] + f[v][st[i]][x]);
g[u][st[i]][j] = std::min(g[u][st[i]][j], g[u][st[i]][j - x] + f[v][u][x]);
}
}
}
}
for(int i = 1; i <= top; i++) {
for(int j = k; j >= 1; j--) {
f[u][st[i]][j] = std::min(f[u][st[i]][j] + w[u] * (dis[u] - dis[st[i]]), g[u][st[i]][j - 1]);
}
f[u][st[i]][0] += w[u] * (dis[u] - dis[st[i]]);
}
top--;
}
void Solve() {
std::cin >> n >> k;
for(int i = 1; i <= n; i++) {
int v, d;
std::cin >> w[i] >> v >> d;
add(v, i, d);
}
dfs(0);
std::cout << f[0][0][k] << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}