没有必要顺着做，讲完树形DP的几道题目就可以讲树上背包的内容然后做树上背包的题，最后尽量做这个题单就可以，如果没做完题单把剩的题标记一下，如果有补充的新题也可以记录一下发我，尽量让学生自己想出来正确的状态和转移，或者给他们指出来为什么他们想的是错的。
10:30–12:15
下午1:30–5:15
树形背包、树形DP是什么，以及树上背包题单
树形DP 树上背包 DAG上的DP
P1352 没有上司的舞会 树形DP √ https://www.luogu.com.cn/problem/P1352
状态表示
状态计算
选 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 void dfs (int u, int fa) son[u] = 1 ; f[u][1 ] = (int )(e[u].size ()); 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题库
作为树上背包的模板例题引入。
