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 点截止的状态比较,取其中的较大值。即

1
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] 就是我们所需的点。因此不需要我们重新计算出我们想要的答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}
algorithm