最近在練樹形 DP，正好看到 這一道 虛標的紫題，但本蒟蒻不會寫，想出來了便記錄一下

題面 & 思考

先看題面，一顆有根樹，選定 k 個節點作為 ”伐木場“，求運送木料最小費用。注意木料費用是 dis * wood。

最開始想到簡單的樹形揹包，狀態轉移方程：

1
f[i][k] = min(f[j][s] + cost, f[i][k]);

但是注意到，如果某個後代節點如果是伐木場，cost 不需要計算，所以狀態中還需要儲存後代的伐木場情況。

但是後代中鋸木廠不止一個。考慮到樹有唯一的父親，且同一深度祖先唯一，可以記錄最近的伐木場祖先，作為狀態的一部分。

有 f[i][j][k] 即 i 節點 最近的伐木場祖先為 j，後代（不算自己）有 k 個是伐木場。

但是由於 f 自己也可能是伐木場，轉移方程不同，需要分類討論，於是改成：f[i][j][k][0/1] 其中 0 代表自己不是伐木場， 1 表示自己是伐木場。

狀態轉移方程

因為我們需要列舉祖先，在 DFS 時需要記錄 Fa 陣列：

1
2
3
DFS 開始時：fa[++tot] = x;

結束時：tot--;

簡單記錄祖先 stack。

回溯後，對於當前節點 x 和 子節點 y 每個祖先 ff：

1
2
3
4
先對每個 k 賦初值，對於每種伐木場個數 l：
f[x][ff][l][0] += f[y][ff][0][0]; --> 當前節點不是伐木場，子節點 y 最近伐木場為 l，對任意 f，賦最大值，即 子結點中沒有伐木場。

f[x][ff][l][1] += f[y][x][0][0]; --> 當前節點是伐木場，子節點 y 最近伐木場為 當前節點，對任意 f，賦最大值，即 子結點中沒有伐木場。

然後就是樹形揹包：

1
2
3
4
f[x][ff][l][0] = min(f[x][ff][l][0], f[x][ff][l-s][0] + f[y][ff][s][0]); --> 當前節點不是伐木場，對 y 節點分配 s 個伐木場個數
f[x][ff][l][1] = min(f[x][ff][l][0], f[x][ff][l-s][1] + f[y][x][s][0]); --> 當前節點是伐木場，對 y 節點分配 s 個伐木場個數

唯一的不同是 y 節點最近祖先為 x

注意在列舉 l 時，由於是01揹包，需要倒過來列舉，不然狀態計算會疊加。（很容易理解）

做完了？好像還差一個 cost！

考慮到 祖先節點 ff cost 的貢獻，因為是 當前節點 W 乘以 到 ff 的總距離！

需要計算總距離，維護 dep 陣列，即當前節點到根節點距離，即可！很容易理解。ff 到 x 的距離就是 dep[x] - dep[ff]

對於當前節點 x 每一個祖先 ff：

1
2
3
4
5
6
7
8
if(l>=1){ --> 因為 l 需要 -1 ，要分類討論。
    f[x][ff][l][0] = min(f[x][ff][l][0] + W[x] * (dep[x]-dep[ff]), f[x][ff][l][1]);
    合併 0 和 1，因為回溯之後，1 的狀態不再被使用，便於下一步計算。
    -1 是因為上文 f[x][ff][l][1] = min(f[x][ff][l][0], f[x][ff][l-s][1] + f[y][x][s][0]); 時，s+l-s = l 但是當前節點也是伐木場，所以狀態更新是 l+1 的，要 -1 獲取正確結果
}else{
    l = 0 時，當前節點不可能為伐木場，直接新增到 ff 增加的貢獻
    f[x][ff][l][0] += W[x] * (dep[x]-dep[ff]);
}

這裡再來聊一聊合併。為了便於討論，上文揹包轉移的時候，我們沒有考慮 y 的 1 的情況，而是在每次 y 回溯時 合併 0 和 1。這有點類似於滾動陣列？回溯後 0 不再表示之前的意義，而是我們最初設計的狀態：i 節點 最近的伐木場祖先為 j，後代（或自己）有 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
74
75
76
77
78
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

struct Node {
    int to, next, d;
} NDS[201];

int head[201], vis[201];
int cnt = 0;
long long W[201];
int tot = 0;

void add(int a, int b, int d) {
    NDS[cnt].to = b;
    NDS[cnt].next = head[a];
    NDS[cnt].d = d;
    head[a] = cnt++;
}

int fa[201];
long long f[201][201][52][2];
long long dep[201];
long long n, k;

void dp(int x) {
    fa[++tot] = x;
    vis[x] = 1;
    for (int i = head[x]; i != -1; i = NDS[i].next) {
        int y = NDS[i].to;
        if (vis[y]) continue;
        dep[y] = dep[x] + NDS[i].d;
        dp(y);
        for (int j = tot; j >= 1; j--) {
            int ff = fa[j];
            for (int l = k; l >= 0; l--) {
                f[x][ff][l][0] += f[y][ff][0][0];
                f[x][ff][l][1] += f[y][x][0][0];
                for(int s = l; s>=0; s--){
                    f[x][ff][l][0] = min(f[x][ff][l][0], f[x][ff][l-s][0] + f[y][ff][s][0]);
                    f[x][ff][l][1] = min(f[x][ff][l][1], f[x][ff][l-s][1] + f[y][x][s][0]);
                }
            }
        }
    }
    for (int j = 1; j <= tot; j++) {
        int ff = fa[j];
        for (int l = k; l >= 0; l--) {
            if(l>=1){
                f[x][ff][l][0] = min(f[x][ff][l][0] + W[x] * (dep[x]-dep[ff]), f[x][ff][l-1][1]);
            }else{
                f[x][ff][l][0] += W[x] * (dep[x]-dep[ff]);
            }

        }
    }

    tot--;
}

int main() {
    
    memset(head, -1, sizeof(head));
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int w, v, d;
        cin >> w >> v >> d;
        W[i] = w;
        add(i, v, d);
        add(v, i, d); 
    }
    dp(0);
    cout << f[0][0][k][0] << endl; 
    return 0;
}