题目简述
一个颗以 0 号节点为根的树，每个点产一些木头，0 号节点有一个伐木场，还需要在 $k$ 个结点修建伐木场。对于每一个点，它的花费是它木头产量乘它到 0 号节点的路径中离它最近的伐木场的距离。最小化总花费。
思路
首先考虑设 $f_{i,j}$ 表示以 $i$ 为根的子树中建了 $j$ 个伐木场，子树中的最小花费。但是有一个明显的问题：如果 $i$ 没有建伐木场，对于子树中的一些节点，我们就不知道它们的木头运到了哪里。所以不这道题中不仅要考虑子树的范围，还需要用离根节点最近的伐木场距离来限制状态。每个节点的木头只能向跟的方向运，所以即使离根节点最近的伐木场不同，对这颗子树的花费产生贡献的点是相同的。
设 $f_{x,i,j}$ 表示以 $x$ 为根的子树中建了 $j$ 个伐木场，$x$ 没有建伐木场，距离 $x$ 最近的伐木场在 $i$； $g_{x,i,j}$ 表示以 $x$ 为根的子树中建了 $j$ 个伐木场，$x$ 建了伐木场，距离 $x$ 最近的伐木场在 $i$ —— 当然也可以用 $f_{x,i,j,\ 0/1}$ 表示这两种状态。下面用 0 表示没有建，1 表示建了。因为 DFS 回溯时更新完的状态不会再被改变，只会被使用，于是我们可以将 0 和 1 记录的答案汇总到一起（下面的部分都是汇总到 0），于是不难得到转移方程。这个点的所有更新结束后再汇总信息。
f[x][father][subk][0] = min(f[x][father][subk][0], f[thisSon][father][l][0] + f[x][father][subk-l][0]);
f[x][father][subk][1] = min(f[x][father][subk][1], f[thisSon][x][l][0] + f[x][father][subk-l][1]);
更新时涉及到枚举根节点祖先的问题，我们可以建一个栈，在第一次 DFS 到某个点时将其入栈，在这个点的更新和信息合并结束后再将其出栈，枚举一个点的祖先是只需要遍历一遍栈就可以了。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 102;
int n, k, w[MaxN], d[MaxN], head[MaxN], cntEdge, f[MaxN][MaxN][MaxN][2], stack[MaxN], top, dis[MaxN];
bool visited[MaxN];
struct Edge{
int destination, value, nextEdge;
}edge[MaxN*2];
#define thisSon edge[i].destination
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void AddEdge(int u, int v, int w){
cntEdge++;
edge[cntEdge].destination = v;
edge[cntEdge].value = w;
edge[cntEdge].nextEdge = head[u];
head[u] = cntEdge;
return;
}
inline void DFS(int x){
stack[++top] = x;
for(int i = head[x]; i; i = edge[i].nextEdge){
if(visited[thisSon]) continue;
visited[thisSon] = true;
dis[thisSon] = dis[x] + edge[i].value;
DFS(thisSon);
for(int j=top; j>=1; j--){
int father = stack[j];
for(int subk = k; subk>=0; subk--){
f[x][father][subk][1] += f[thisSon][x][0][0];
f[x][father][subk][0] += f[thisSon][father][0][0];
for(int l=subk; l>=0; l--){
f[x][father][subk][0] = min(f[x][father][subk][0], f[thisSon][father][l][0] + f[x][father][subk-l][0]);
f[x][father][subk][1] = min(f[x][father][subk][1], f[thisSon][x][l][0] + f[x][father][subk-l][1]);
}
}
}
}
for(int i=1; i<=top; i++){
int father = stack[i];
for(int j=k; j>=0; j--){
if(j >= 1) f[x][father][j][0] = min(f[x][father][j][0] + w[x] * (dis[x]-dis[father]), f[x][father][j-1][1]);
else f[x][father][j][0] += w[x] * (dis[x]-dis[father]);
}
}
top--;
return;
}
signed main(){
n = Read(), k = Read();
for(int i=1; i<=n; i++){
w[i] = Read();
int father = Read();
d[i] = Read();
AddEdge(father, i, d[i]);
}
visited[0] = 1;
DFS(0);
printf("%lld", f[0][0][k][0]);
return 0;
}