从树形dp到树上背包

1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。

Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计算到他对答案的贡献。所以问题转化为：求以i为根的最大子树权值和。

  • 对于这个问题我们直接进行dp即可。dp[i]表示在i的子树里面，包含i的联通块的最大权值和。转移就是dp[u]=a[u]+∑v∈son[u]max⁡(0,dp[v])dp[u]=a[u]+ \sum_{v \in son[u]} \max(0,dp[v])
  • 一个实现细节是：我们必须不能选择空集，所以我们需要保证我们的答案初始值足够小，是负无穷。
  • 几乎一模一样的阅读理解题https://www.luogu.com.cn/problem/P5766
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
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = -INT_MAX;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> dp(n + 1);
    auto dfs = [&](auto self, int u, int fa) ->void{
        dp[u] = a[u];
        for (auto v : e[u]) {
            if (v == fa)
                continue;
            self(self, v, u);
            dp[u] += max(0, dp[v]);
        }
        ans = max(ans, dp[u]);
    };
    dfs(dfs, 1, 1);

    cout << ans << endl;
}

上下界优化树形背包再谈树上背包的上下界优化 - Liuxizai’s Blog

以选课这个题为例题，体积为1的树形背包：我们直接做复杂度是O(nm2)O(nm^2)的

[P2014 CTSC1997] 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

问题：给定一棵树，每个点有点权，找到大小为m的最大联通块，要求满足树形祖先依赖

Sol：考虑dp[u][j]dp[u][j]表示u节点选了jj体积的点，每次将一个儿子合并更新到dp[u]dp[u]，具体转移是dp[u][j]=max⁡k≤j,v∈son[u]dp[v][k]+dp[u][j−k]dp[u][j]=\max_{k \le j,v \in son[u]}dp[v][k]+dp[u][j-k].考虑原地修改的话我们需要倒着枚举jj,保证本轮的状态不被本轮前面状态更新。每次最后再把自己u这个节点的贡献更新进去，注意这里是必须更新的，而不是取max。

  • 因为考虑u节点的话，我们就必须选择u节点。

    • j≥weight[u]:dp[u][j]=dp[u][j−weight[u]]+value[u]j \ge weight[u] :dp[u][j]=dp[u][j-weight[u]]+value[u]
    • j<weight[i]:dp[u][j]=0j<weight[i]:dp[u][j]=0

    O(nm2)O(nm^2)Code：关于本题的实现细节有是一个森林，不利于我们直接dp。不然最后还要单独处理联通块之间的合并，考虑建立虚根，体积为0，价值为0。因此需要在最后合并当前节点的时候特判跳过u=1节点。

    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
    void solve() {
        int n, m;
        cin >> n >> m;
        int ans = 0;
        vector dp(n + 2, vector<int>(m + 1));
        vector<vector<int>> e(n + 2);
        vector<int> val(n + 2);
        for (int i = 2; i <= n + 1; i++) {
            int fa;
            cin >> fa >> val[i];
            if (fa == 0)
                e[1].push_back(i);
            else {
                fa++;
                e[fa].push_back(i);
            }
        }
        auto dfs = [&](auto self, int u) -> void {
            for (auto v : e[u]) {
                deb(u, v);
                self(self, v);
                for (int j = m; j >= 0; j--) {
                    for (int k = 0; k <= j; k++) {
                        dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]);
                    }
                }
            }
            if (u > 1) {
                for (int j = m; j >= 1; j--) dp[u][j] = dp[u][j - 1] + val[u];
                dp[u][0] = 0;
            }
        };
        dfs(dfs, 1);
        ans = *max_element(alls(dp[1]));
        cout << ans << endl;
    }

    • 需要倒序枚举 i 防止状态在转移前被覆盖。否则的话dp数组要多一维。

    • 另一种处理虚根的方法，改变体积。由于可能是森林，所有没有直接先修课的节点，可以父亲视为节点 0，然后实际上就要选 m+1 个节点

发现可以进行背包枚举的上下界优化：每次合并子树背包的代价是O(siz[u]×siz[v])O(siz[u] \times siz[v])。对于任意一对点，它们只会在lca(u,v)lca(u,v)被合并计算贡献一次，所以这个问题的时间复杂度变成了O(n2)O(n^2)

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
void solve() {
    int n, m;
    cin >> n >> m;
    int ans = 0;
    vector dp(n + 2, vector<int>(m + 1));
    vector<vector<int>> e(n + 2);
    vector<int> val(n + 2), sz(n + 2);
    for (int i = 2; i <= n + 1; i++) {
        int fa;
        cin >> fa >> val[i];
        if (fa == 0)
            e[1].push_back(i);
        else {
            fa++;
            e[fa].push_back(i);
        }
    }
    auto dfs = [&](auto self, int u) -> void {
        if (u > 1)
            sz[u] = 1;
        for (auto v : e[u]) {
            deb(u, v);
            self(self, v);
            sz[u] += sz[v];
            for (int j = min(sz[u], m); j >= 0; j--) {
                for (int k = 0; k <= min(j, sz[v]); k++) {
                    dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]);
                }
            }
        }
        if (u > 1) {
            for (int j = min(m, sz[u]); j >= 1; j--) dp[u][j] = dp[u][j - 1] + val[u];
            dp[u][0] = 0;
        }
    };
    dfs(dfs, 1);
    ans = *max_element(alls(dp[1]));
    cout << ans << endl;
}

上面这份代码还能解决的问题是当n是1e51e5级别的时候，m是1e31e3,这样的话我们会发现体积这一维应该只需要算到min⁡(m,sz[u])\min(m,sz[u])。合并子树代价是O(min⁡(sz[u],m))×O(min⁡(sz[v],m))O(\min(sz[u],m)) \times O(\min(sz[v],m)),可以证明这样的时间复杂度是O(nm)O(nm)

image-20241004022533759

图片为感性理解，以上两个时间复杂度的数学证明链接：树上背包的上下界优化 - ouuan的博客

总结： 1. 如果合并两个子树的代价等于树的大小的乘积的话，那么复杂度就是O(n2)O(n^2)的

  1. 如果合并两个子树的代价等于子树大小和m取min的乘积的话，复杂度就是O(nm)O(nm)的
  2. 如果不是这样，就没有相应的结论，比如合并的代价是$O((su + sv)^2) $
  3. 如果是距离相关的话，因为距离不会超过子树的大小，所以有类似的结论

第一阶段总结：们知道对于树上背包，若每个结点上只有总大小为 O(1)O(1) 的物品，则总复杂度为 O(n2)O(n^2)；若再限制背包大小为 m，则总复杂度为 O(nm)O(nm)。

  • 上面这种做法比较好写，而且还有一个优点，就是它事实上求出了每棵子树的 dp 值，换句话说，它可以统计到每个连通块的答案。当然，它也有一定的局限性，那就是第二维必须和子树的大小有关，否则复杂度就不对了。
  • 这些实现无法解决多重背包，亦无法解决物品大小不为 1 的情况。此时，一个结点子树内的总物品数不再与子树大小同级，不适用之前的复杂度分析，由于在每个结点上我们都需要对儿子的背包进行非平凡的合并，总复杂度容易上升至 O(nm2)O(nm^2)。
  • dfs 序优化的树上依赖性背包则避免了合并背包这一操作。

结论：节点体积为任意，背包限制是 m 的时间复杂度是 O(Vm)O(Vm)，V是∑abs(weight[i])\sum abs(weight[i])但其实际效果可能只有理论复杂度的120\frac{1}{20}

dfs 序优化树上依赖性dfs 序优化树上依赖性背包学习笔记 - Liuxizai’s Blog

形式化的，树上依赖性背包指的是这样一类问题：若在某结点上选取了物品，则必须在其所有祖先上选取物品。

我们考虑直接在树的 dfs 序上进行 dp，在每个结点处我们都有两种决策：

  • 选取至少一个物品，然后进入子树继续选取物品。
  • 什么都不选，跳过当前子树。

具体问题构建：一棵树每个点有体积和价值，背包体积为M，n个点也就是n个物品，具有树形依赖。保证n×m≤6e7n \times m \le6e7

题外话：如何给这种输入的数据限制开二维dp的C_array,动态给指针分配内存

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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> dp_pool;  // 全局内存池
int **dp;             // DP数组指针
int n, m;             // n: 行数, m: 列数

// 函数：动态分配内存
void allocate_dp_array(int n, int m) {
    dp_pool.resize(n * m);  // 分配一维内存池
    dp = new int *[n];      // 分配指针数组
    for (int i = 0; i < n; ++i) {
        dp[i] = dp_pool.data() + i * m;  // 每个指针指向内存池中相应的起始位置
    }
}

// 示例：清理分配的内存
void deallocate_dp_array() {
    delete[] dp;   // 释放指针数组
    dp = nullptr;  // 设置为nullptr以避免悬挂指针
}

int main() {
    n = 5;   // 例如，5行
    m = 10;  // 例如，10列
    allocate_dp_array(n, m);

    // 示例使用：初始化DP数组
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i][j] = i + j;  // 填充示例数据
        }
    }

    // 打印结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    deallocate_dp_array();  // 释放内存
    return 0;
}

同样代码可以解决的题：每个点都有权值和重量，求一个重量恰好为k的包含根的连通块，最大的权值和

Sol:考虑按dfs序做，r[u]+1r[u]+1表示序列中跳过x的子树的下一个位置，dp[i][j]dp[i][j]表示dfs序中 [i, n+1] 这一段的节点重量等于j的最大权值。转移：dp[i][j]=max⁡(dp[r[i]+1][j],dp[i+1][j−wei[id[i]]]+val[id[i]])dp[i][j]=\max(dp[r[i]+1][j],dp[i+1][j-wei[id[i]]]+val[id[i]])

  • 如果不选第i个节点，则直接跳过i整个子树，从r[i]+1转移过来

  • 选第ii个的节点的前提是j>=wei[u]j>=wei[u]，id[i]id[i]表示dfs序为i的节点在树上的真实编号，从i+1转移过来。

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
void solve() {
    int n, m;
    cin >> n >> m;
    // dfn:useful(1-n+1),init(n+2=-inf),(0_space);
    vector dp(n + 3, vector<int>(m + 1));

    for (int i = 1; i <= m; i++)
        dp[n + 2][m] = -inf;

    vector<vector<int>> e(n + 1);

    for (int i = 1; i <= n; i++) {
        int fa;
        cin >> fa;
        e[fa].push_back(i);
    }

    vector<int> wei(n + 1), val(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> wei[i];

    for (int i = 1; i <= n; i++)
        cin >> val[i];

    vector<int> l(n + 1), r(n + 1), id(n + 2);
    int idx = 0;
    auto dfs = [&](auto self, int u) -> void {
        l[u] = ++idx;
        id[idx] = u;

        for (auto v : e[u]) {
            self(self, v);
        }

        r[u] = idx;
    };
    dfs(dfs, 0);

    for (int i = n + 1; i >= 1; i--) {
        int u = id[i];

        for (int j = 0; j <= m; j++) {
            if (j >= wei[u])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - wei[u]] + val[u]);

            dp[i][j] = max(dp[i][j], dp[r[u] + 1][j]);
        }
    }

    cout << dp[1][m] << endl;
}

多叉树变二叉树，泛化物品222222222222222[笔记]树形dp - 2/4（树上背包类） - Sinktank - 博客园 (cnblogs.com)

分块续4444444444444PermuTree (hard version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

44444444444444ICPC2023济南站题解（A B D E G I K M） - maple276 - 博客园 (cnblogs.com)

PermuTree (easy version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分块续444444444444The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan) - 空気力学の詩 - 博客园 (cnblogs.com)

练习1：在树上找一个连通块，满足任意两点之间的距离都不超过d,使得权值之和最大，权值可能是负数

Sol:$ f[i][j]:表示i这个子树里面，选择一个包括i的连通块，并且这个联通块中∗∗距离i这个点最远距离∗∗是j那么合并子树的联通块的时候，对于:表示i这个子树里面，选择一个包括i的连通块，并且这个联通块中**距离i这个点最远距离**是j 那么合并子树的联通块的时候，对于f[v1][j1]，f[v2][j2]两个子树,他们需要满足两个子树,他们需要满足j1+j2+2<=d并且将结果更新到并且将结果更新到 f[u][max(j1, j2)+1]$里面去

练习2：在树上找一个点集，满足任意两点之间的距不小于d，使得权值之和最大，权值可能是负数

Sol:f[i][j]：f[i][j]：表示在i个子树里面选一个点集，并且这个点集里面的点距离i的最小距离是j，当然如果j==0就表示选了i这个
点, 那么合并子树的时候，f[v1][j1],f[v2][j2]f[v1][j1],f[v2][j2], 需要满足j1+j2+2>=dj1+j2+2>=d并且将结果更新到f[u][min(j1,j2)+1]f[u][min(j1, j2)+1]当中

3.题意:给定一棵n个节点的树,求留下一棵m个结点的子树，最少需要切断几条边?https://www.luogu.com.cn/problem/U53878

Sol：首先可以有这么一个想法：设$ f[u][s]$ 表示在节点 u ，获得大小为s的子树所需要删除的边的个数。

image-20241008140217515

最后计算答案的时候应该注意dp[u][m]dp[u][m]强制选择了u节点，但答案不一定选u节点，所以考虑ans=min⁡u∈[1,n]dp[u][m]ans=\min_{u \in[1,n]}{dp[u][m]}.进一步修正，考虑如果一个非根节点u像作为最终答案还需要砍掉u和fa[u]fa[u]那条边，ans=min⁡(dp[1][m],dp[u][m](u∈[2,n]))ans=\min(dp[1][m],dp[u][m](u \in [2,n]))

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
void solve() {
    int n, m;
    cin >> n >> m;
    vector dp(n + 1, vector<int>(m + 1, inf));
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    vector<int> sz(n + 1);
    // 强制选u，且以u为根的子树中包含j个点，所需要删边最小数目
    auto dfs = [&](auto self, int u) -> void {
        dp[u][1] = 0;  // 初始的时候考虑没有子树
        sz[u] = 1;
        for (auto v : e[u]) {
            deb(u, v);
            self(self, v);
            sz[u] += sz[v];
            for (int j = min(m, sz[u]); j >= 1; j--) {
                dp[u][j] += 1;  // k=0不分配体积给v，需要删1条边
                for (int k = 1; k <= min(sz[v], j - 1); k++) {
                    dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);
                }
            }
        }
    };
    dfs(dfs, 1);
    int ans = dp[1][m];
    for (int i = 2; i <= n; i++) ans = min(ans, dp[i][m] + 1);
    cout << ans << endl;
}

4.https://www.luogu.com.cn/problem/P1273给定一棵树，边有边权，叶子节点有点权。选择一个连通块，满足树上依赖关系(也就是选了u点，u到根的点都必须选),最大化这个联通块的价值。

  • 价值定义为联通块中所有叶子的点权−所有边的边权所有叶子的点权-所有边的边权

Sol: 设f[i][j]f[i][j]表示以i为根的子树内选出j个叶子节点的最大权值和.考虑枚举子节点选了k个叶子节点

  • k=0k=0 dp[u][j]−>dp[u][j]+dp[v][k]dp[u][j]->dp[u][j]+dp[v][k],又因为dp[v][k]=0dp[v][k]=0,所以相当于没更新
  • k>0 dp[u][j]=max(dp[u][j],dp[u][j−k]+dp[v][k]−w)dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-w)，说明必须连u和v这条边，也就是必须付出w的代价。
  • 可以维护sz[u]表示u的子树中叶子节点的数量，从而进行上下界优化。
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
struct edge {
    int v, w;
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> e(n + 1);
    vector<int> val(n + 1);
    vector dp(n + 1, vector<int>(m + 1, -inf));
    for (int i = 1; i <= n - m; i++) {
        int num;
        cin >> num;
        for (int j = 1; j <= num; j++) {
            int v, cost;
            cin >> v >> cost;
            e[i].push_back({v, cost});
        }
    }
    vector<int> sz(n + 1);
    for (int i = n - m + 1; i <= n; i++) cin >> val[i];
    auto dfs = [&](auto self, int u) -> void {
        dp[u][0] = 0;  // 这里初始化很重要
        if (u >= n - m + 1) {
            sz[u] = 1;
            dp[u][1] = val[u];  // 这个只能对叶子做，非叶子要保持-inf
        }
        for (auto [v, w] : e[u]) {
            self(self, v);
            sz[u] += sz[v];
            for (int j = min(m, sz[u]); j >= 1; j--) {      // 至少选一个
                for (int k = 1; k <= min(j, sz[v]); k++) {  // 可以全给当前这个，不是依赖
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
                    // 写出k=0式子发现相当于没更新，感性理解
                    // 新子树一个都不选当然无法更新当前根节点的dp值
                }
            }
        }
    };
    dfs(dfs, 1);
    int ans = 0;
    for (int i = 1; i <= sz[1]; i++) {
        if (dp[1][i] >= 0) {
            ans = i;
        }
    }
    cout << ans << endl;
}