题面

题意

这道题的大致意思就是，在一个以0号节点为根的树上，我需要在k个结点修建伐木场。然后对于每一个点，它对答案的贡献是他木头产量乘上它离下游最近伐木场的距离。让你合理分配伐木场安置距离以使得贡献最小。

分析

其实很容易就会想到用$f_{i,j}$来表示在i号点为根的子树上修建j个伐木场所得的最小贡献，但是我们发现状态并不好维护，所以我们需要改变一定的想法。

我们这里采用$f_{i,j,k}$表示在i为根的子树上修建k个伐木场，并且i下游的第一个伐木场在j，然后该状态下贡献的最小值。然后我们再记录$g_{i,j,k}$为i号点上建造伐木场，并且在i的子树上一共有k个伐木场，i下游的第一个伐木场是j，然后该状态下的最小值。

所以我们只要最后推到$f_{0,0,k}$然后输出就是最后答案了。

再考虑动态转移方程，很容易想到转移的过程就是一个背包的过程，然后为了记录某一结点所有的祖先，所以我们可以在dfs里加上手写栈（我比较懒，用了一个deque），这样只需要遍历栈就可以知道该点所有的祖先。

代码

简单背包模拟即可。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

struct edge
{
    int to, dist;
};

vector<vector<edge> > graph;

int c[maxn], depth[maxn];
long long f[maxn][maxn][maxn], g[maxn][maxn][maxn];
deque<int> st;
int n, k;

void dfs(int p)
{
    st.push_back(p);
    for (vector<edge>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
    {
        depth[i->to] += depth[p] + i->dist;
        dfs(i->to);
        for (deque<int>::iterator j = st.begin(); j != st.end(); j++)
            for (int l = k; ~l; l--)
            {
                f[p][*j][l] += f[i->to][*j][0];
                g[p][*j][l] += f[i->to][p][0];
                for (int x = 0; x <= l; x++)
                {
                    f[p][*j][l] = min(f[p][*j][l], f[p][*j][l - x] + f[i->to][*j][x]);
                    g[p][*j][l] = min(g[p][*j][l], g[p][*j][l - x] + f[i->to][p][x]);
                }
            }
    }
    for (deque<int>::iterator j = st.begin(); j != st.end(); j++)
    {
        f[p][*j][0] += c[p] * (depth[p] - depth[*j]);
        for (int l = 1; l <= k; l++)
            f[p][*j][l] = min(f[p][*j][l] + c[p] * (depth[p] - depth[*j]), g[p][*j][l - 1]);
    }
    st.pop_back();
    return;
}

int main()
{
    // freopen("riv.in", "r", stdin);
    // freopen("riv.out", "w", stdout);
    scanf("%d%d", &n, &k);
    graph.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int fa, dist;
        scanf("%d%d%d", c + i, &fa, &dist);
        graph[fa].push_back((edge){i, dist});
    }
    dfs(0);
    printf("%d\n", f[0][0][k]);
    return 0;
}