P3354 Riv 河流

题意

有一个 n + 1 个节点的树，其中 0 号节点为根。每个节点上都有一些物品，每个边都有长度。现在所有的物品只能朝着根的方向前进，现在设置k节点作为终点。问所有物品的移动距离之和最小是多少。

思路

首先，如果我们要求解其最小花费，我们发现其情况过于复杂。但是如果我们从另一个角度来看这个题目的话，就会变的简单许多。原本，u 节点到 0 点需要 deep[u] * w[u] 这么多的花费，如果我们在这里设置中终点，那么这些节点的花费就被我们省下来了。对于原本属于 u 的子树中的所有节点，如果它原本是要到终点。那么同样的也将省下来 deep[u] * w[x]。

因此我得到如下的策略，每次计算出来节省的最多的花费。

我们设置如图所示的状态。

alt

首先我们假设，我们现在要求的节点状态是 u 节点，那么对于其所有子树的节点，其节省的花费可以分成两种情况，要么到 u 停止，要么到其中的某个节点停止。对于第一种，我们的节省的花费就是 w[x] * deep[u] 。对于第二种所节省的花费，我们已经在停止的那个节点上算过了，就是 dp[i][k] 。

那么这个时候，我们不妨以 u 为根，算出来，如果以 u 为截止的点所有的 f[x][k] 。

我们在计算 f[x][k] 的时候，我们首先有这样的状态 f[x][0] = w[x] * deep[u] 。之后我们计算其状态的时候，我们要依据其子树的状态，假若其子树为 v。那么我们便可以得到这样的状态转移方程。

f[x][i+j] = \max\limits_{i+j <k}(f[x][i] , f[v][j]);

这里有个细节需要注意一下，我们最后得到的 f[x][i+j] 是通过上一个状态转移而来，因此，我们不能以当前转移过来的状态，作为我们现在即将转移的状态，关于此方面的叙述详见背包的滚动数组优化。

在计算完成之后，我们的 f[x][k] 还需要和原本表示在 x 点截止的状态比较，取其中的较大值。即

for (int i = 0; i <= k ; i ++ ) f[x][i] = max(f[x][i] , dp[x][i]);

那么在最后，我们计算完所有子树的结点 x 了之后，我们现在着手 u 节点。

同上述的状态转移方程相同，我们计算 f[u][k] 。但与上面的不同的是，因为 u 节点即为自身，并且我们选择在 u 节点停止，所以我们不能设置初始状态 f[u][0] = w[u] * deep[u] 。因此，我将 u 节点放作最后计算。

计算完 f[u][k] 后，我们将节点 u 加入，也就是这样的方程 dp[u][i] = f[u][k - 1] + w[u] * deep[u]。

那么至此，我们也就求完了所有的 dp[u][x]。

值得注意的是，我们最后求的点 f[0][k] 就是我们所需的点。因此不需要我们重新计算出我们想要的答案了。

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

vector<pair<int, LL>> E[110];
LL w[110], dis[110];
LL dp[110][55], f[110][55];
int n, k;
int sz[110];

LL tot = 0;

void init(int u, LL deep = 0) {
    sz[u] = 1;
    dis[u] = deep;
    tot += w[u] * deep;
    for (auto [x, y] : E[u]) {
        init(x, deep + y);
        sz[u] += sz[x];
    }
}

void g(int u, int tar) {
    if (tar != u) f[u][0] = dis[tar] * w[u];
    for (auto [x, y] : E[u]) {
        g(x, tar);
        for (int i = k; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[u][i] = max(f[u][i], f[x][j] + f[u][i - j]);
            }
        }
    }

    for (int i = 0; i <= min(k, sz[u]); i++) {
        f[u][i] = max(f[u][i], dp[u][i]);
    }
}

void dfs(int u) {
    for (auto [x, y] : E[u]) {
        dfs(x);
    }
    memset(f, 0, sizeof(f));
    g(u, u);

    if (u)
        for (int i = min(k, sz[u]); i > 0; i--)
            dp[u][i] = f[u][i - 1] + dis[u] * w[u];
}

int main() {
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        int f, l;
        cin >> f >> l;
        E[f].emplace_back(i, l);
    }

    // exit(0);

    init(0);

    dfs(0);

    cout << tot - f[0][k] << '\n';

    return 0;
}