Running-Turtle

My blogs

0%

2025-01-17 市南

发表于 分类于

没有必要顺着做，讲完树形DP的几道题目就可以讲树上背包的内容然后做树上背包的题，最后尽量做这个题单就可以，如果没做完题单把剩的题标记一下，如果有补充的新题也可以记录一下发我，尽量让学生自己想出来正确的状态和转移，或者给他们指出来为什么他们想的是错的。

10:30–12:15

下午1:30–5:15

树形背包、树形DP是什么，以及树上背包题单

树形DP 树上背包 DAG上的DP

P1352 没有上司的舞会 树形DP √

https://www.luogu.com.cn/problem/P1352

状态表示

  • f[u][1] 表示以 u 为根节点的子树并且包括 u 的总快乐指数

  • f[u][0] 表示以 u 为根节点的子树并且不包括 u 的总快乐指数

状态计算

  • 选 u , $f[u][1]+=\sum f[son][0]$

  • 不选 u , $f[u][0]+=\sum max(f[son][1],;f[son][0])$

1
2
3
4
5
6
7
8
9
void dfs(int u){
    f[u][1]=r[u];
    for(int i=h[u]; i!=-1; i=ne[i]){
        int v=e[i];
        dfs(v);
        f[u][0]+=max(f[v][1], f[v][0]);
        f[u][1]+=f[v][0];
    }
}

通过 DFS，在返回上一层时更新当前结点的最优解。

、、树形DP经典题目。

、、$dp_{u,0/1}$ 代表是否选节点 u，以节点 u 为根的子树能得到的最大快乐值。

P4084 USACO17DEC] Barn Painting G 树形 DP √

https://www.luogu.com.cn/problem/P4084

n 个结点的树，k 个结点染色了，剩下的结点每个可以染色 3 种，求最终方案数 ？

设 $dp_{u,0/1/2}$ 表示以 u 为根的子树，染色为 0/1/2 的方案数。

$dp_{u,c}*=dp_{v,1/2/3}$ ，注意染色不能相同，注意初始化问题

P2016 战略游戏 树形DP√

最少点覆盖所有边问题

$dp_{u,0/1}$ 表示以 u 为根的子树，是否选择在 u 点布置士兵，覆盖子树所有边的最小方案数。

P1122 最大子树和 树形DP √

求最大子树和

设 $dp_u$ 是以 u 为根的最大子树，那么答案一定是 $\max dp_i$

注意这里答案不一定是 $dp_1$ 。

对于以根 r 为根的树来说，答案的联通块一定是以其中某一个点作为根节点的包括一部分点的子树、所以可以枚举 $dp_i$ 。

P3478 换根DP例题 √

换根DP入门文章

https://zhuanlan.zhihu.com/p/2084665478 有详细讲换根DP。

P2986 换根DP应用 √

先考虑 f, $cow_u$ 表示 $T_1$ 中以 u 为根的奶牛的数量之和。

$f_u=\sum(f_v + w\times cow_v)$

$g_v=g_u-cow_v\times w + (sumCow-cow_v)\times w$

CF1689C 思维 + 树形DP √

acyclic 无环的

Problem - 1689C - Codeforces

可以发现题目给定的是一个二叉树。

设 $dp_u$ 表示以 u 为根的子树，u 感染了，最多 save 几个。

若 $out_u=1$ , 拯救 $son_u-2$ 个（删儿子）

若 $out_u=0$ , 0 个

若 $out_u=2$ ，删左儿子或者右儿子

CF1092F 换根DP , 基础换根的式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs1(int u, int fa) {
    sa[u] = a[u];
    for(int v : e[u]) {
        if(v == fa) continue ;
        dfs1(v, u);
        sa[u] += sa[v];
        f[u] += f[v] + sa[v];
    }
}

void dfs2(int u, int fa) {
    for(int v : e[u]) {
        if(v == fa) continue ;
        g[v] = g[u] + suma - 2 * sa[v];
        dfs2(v, u);
    }
}

CF1693B

P2052 道路修建 树形DP √

设 $son_u$ 表示以 $u$ 为根的子树有多少个点。

对于道路 $(u,v,w)$ ，u 为父节点，费用是 $w*|(n-son_v)-son_v|$ 。

CF120F

P2015 树形背包例题二 √

读题。以 1 为根的子树。

对于 (u,v), 选择 v，就得选择 u，所以树形背包，就是有依赖的一种树形DP。

设 $f_{u,x}$ 表示以 u 为根的苹果树，保留 x 个枝条的最大苹果树。

先枚举 x，对于每个 v 点，类似于 01 背包，枚举每个点的决策-即每个点选多少个体积来用，

所以 $f_{u,x}=max(f_{v,s}+f_{u,x-s},f_{u,x})$ ，这是一般的树形背包的形式，本题保留的树枝，想让 u 跟 v 连接，至少保留一根树枝。

$f_{u,x}=\max(f_{u,x},f_{v,s}+f_{u,x-s})$ 。

CF212E

AT_abc287_f

AT_abc207_f

CF815C

P1272 树形背包题目 √

https://blog.csdn.net/weixin_72060925/article/details/129442749

设 $f_{u,x}$ 表示保留以 u 为根的子树的 x 个点，最少删多少条边。

$f_{u,1}=e_u.size()$ ，即删除该点的所有出边以及其与父节点的边。

$f_{u,i}=\min (f_{u,i},(f_{v,j}-1)+(f_{u,i-j}-1))$ 。

为什么 -1，$f_{v,j}$ 表示删边的时候，默认删除了 $(u,v)$ ，对于 $f_{u,i-j}$ 同理。即它们的值都多算了 1，所以需要减一。

$\text{res}=\min_i f_{i,P}$

在这里插入图片描述 
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
/**
 * f[u][i] 表示以 u 为根的子树, 保留 i 个点, 最少删除多少条边 ?
 */

void dfs(int u, int fa) {
    son[u] = 1;
    f[u][1] = (int)(e[u].size()); // 只保留 u, 需要删多少边
    for(int v : e[u]) {
        if(v == fa) continue ;
        dfs(v, u);
        son[u] += son[v];
        for(int i = son[u]; i >= 1; i --) {
            for(int j = 1; j <= son[v] && j < i; j ++){
                f[u][i] = min(f[u][i], (f[u][i - j] - 1) + (f[v][j] - 1));
            }
        }
    }
}

void solve(){
    cin >> n >> P;
    for(int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            f[i][j] = 1E9;
        }
    }

    dfs(1, 0);

    int res = 2E9;
    for(int i = 1; i <= n; i ++){
        res = min(res, f[i][P]);
    }
    cout << res;
}

补充题目

有依赖的背包问题 树形背包例题引入√

10. 有依赖的背包问题 - AcWing题库

作为树上背包的模板例题引入。