核心逻辑与数学原理
树形背包（Tree-dependent Knapsack），又称有依赖的背包问题，是树形动态规划中最具威力的经典进阶模型。它的核心本质是将图论中的拓扑树状依赖关系与组合数学中的分组背包状态网络进行高维融合。
1. 树状依赖的几何降维
在线性背包问题中，各类物品之间是并列、独立的。而在树形背包中，如果一个节点 $u$ 被选入背包，它的所有子节点 $v \in \text{son}(u)$ 才有资格被放入背包；反之，若父节点 $u$ 未被选择，则其整棵子树将被强制“剪枝”。
这种复杂的拓扑依赖，通过 DFS 的后序遍历可以被局部化解耦：
对于任何一个父节点 $u$，在选定它自身的前提下，它的每一个直接子节点 $v$ 都可以看作是一个独立的分组。分给子树 $v$ 不同的体积 $k$，就会产生不同的最大价值收益。这在本质上就是一个分组背包问题。
2. 多项式乘法与状态卷积的物理意义
设父节点 $u$ 分配给其子树 $v$ 的总体积为 $k$。那么子树 $v$ 内部的各种物品组合，在体积为 $k$ 的限制下所能贡献的最大价值，就是一个完整的、已固化的局部最优状态。父节点 $u$ 把总容量 $j$ 分配给旗下各个子树的过程，在数学上等价于对多个多项式进行状态卷积（Convolution）：
$$f[u][j] = \max \left( f[u][j], f[u][j - k] + f[v][k] \right)$$
其中 $j$ 倒序循环，确保了在更新当前子树 $v$ 的状态时，使用的是尚未被子树 $v$ 污染的父节点前驱状态（严格遵守分组背包的互斥控制）。
状态设计与算法推导
1. 状态空间定义
设 $f[u][j]$ 表示在以 $u$ 为根的子树中，投入总体积（或耗费总资金）恰好或不超过 $j$ 时所能获得的最大价值。
- 核心前提条件：由于依赖关系，要让 $f[u][j]$ 具有合法物理意义，必须默认当前节点 $u$ 已经被强制选入背包。
2. 状态转移方程推导
对于节点 $u$，设其自身体积为 $w[u]$，价值为 $v[u]$。总背包容量为 $V$。
- 基础元状态初始化：
$$f[u][j] = v[u] \quad (\forall w[u] \le j \le V)$$
这表示在不给任何子树分配容量时，仅选择根节点 $u$ 自身的收益。 2. 三层循环卷积转移： 遍历 $u$ 的每一个子节点 $v$：
$$f[u][j] = \max_{w[u] \le j \le V} \left\{ \max_{0 \le k \le j - w[u]} \{ f[u][j - k] + f[v][k] \} \right\}$$
- 内层循环 $k$ 的边界逻辑：分给子树 $v$ 的体积 $k$ 最大不能超过 $j - w[u]$，因为必须强制给父节点自身预留出 $w[u]$ 的空间。
C++ 标准源码（NOIP风格）
以下源码为标准的树形背包实现，采用高性能无向图建树方式加安全哨兵拦截，完美适配 Linux g++ -O2 环境。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 305;
const int MAXV = 305;
int n, m; // n 为节点总数，m 为背包总容量
int w[MAXN], v[MAXN];
int f[MAXN][MAXV];
vector<int> edge[MAXN];
// 树形背包核心：利用 DFS 动态交织背包状态
void dfs(int u, int fa) {
// 1. 强制初始化：只要选了以 u 为根的子树，u 自身必须占据 w[u] 的容量
for (int j = w[u]; j <= m; ++j) {
f[u][j] = v[u];
}
// 2. 枚举子节点（分组背包中的“组”）
for (int v_node : edge[u]) {
if (v_node == fa) continue; // 规避无向边反向死循环
dfs(v_node, u); // 拓扑沉底，先让子节点把自己的背包网络刷出来
// 3. 倒序枚举父节点背包容量（分组背包的经典容量轴）
// 致命踩坑点：必须倒序，且下界是 w[u]，必须留足根节点自身的空间
for (int j = m; j >= w[u]; --j) {
// 4. 枚举分给当前子树 v_node 的容量 k（分组背包中的“组内物品”）
for (int k = 0; k <= j - w[u]; ++k) {
f[u][j] = max(f[u][j], f[u][j - k] + f[v_node][k]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
// 考场小技巧：由于可能存在多棵独立的树（森林结构），
// 建立一个虚拟的“0号超级根节点”，其 w[0]=0, v[0]=0，将森林统一转化为以 0 为根的单棵树
w[0] = 0; v[0] = 0;
for (int i = 1; i <= n; ++i) {
int parent;
cin >> parent >> w[i] >> v[i];
// 建立双向（或单向）拓扑连接
edge[parent].push_back(i);
edge[i].push_back(parent);
}
// 从虚拟根节点 0 启动 DFS
dfs(0, -1);
// 最终答案即为在虚拟根节点投入总容量 m 的最大价值
cout << f[0][m] << "\n";
return 0;
}NOIP 实战避坑指南
1. 三层循环控制顺序错乱导致状态自我污染
- 现象：在回溯更新状态时，写成了先枚举分给子树的容量 $k$，再枚举总容量 $j$。或者在枚举 $j$ 时使用了正序循环
for (int j = w[u]; j <= m; ++j)。这会导致分组背包的互斥限制彻底崩塌，子树 $v$ 的状态会被连续重复加入父节点的背包中，等价于同一个子树被购买了数次，严重违反拓扑逻辑。 - 规避手段：死记树形背包更新的循环控制网格：先枚举子节点（组） $ o$ 再倒序枚举容量 $j$（防止污染） $ o$ 最后枚举分配容量 $k$（组内决策）。
2. 内层循环边界未给父节点预留空间
- 现象：在最内层枚举分给子树的容量 $k$ 时，误写成了
for (int k = 0; k <= j; ++k)。这会导致当 $k = j$ 时，分配给子树的容量吃满了当前的全部预算。由于 $j - k = 0$，父节点的状态被迫去引用 $f[u][0]$。而我们在初始化中知道，父节点在容量低于 $w[u]$ 时的价值全为 0。这种转移在物理语义上等价于“买下了子树的组合，却把处于树根的亲爹给扔了”，直接违反了“选子节点必须先选父节点”的依赖规则。 - 规避手段：内层循环的容量分配上限必须严格控制在
j - w[u]。
经典 NOIP/洛谷 真题
1. 洛谷 P2014 [CTSC1997] 选课
- 题意描述：大学里有 $M$ 门课，每门课有一定的学分。有些课程有先修课（每门课至多只有一门先修课）。一个学生最多只能选 $N$ 门课。求在满足先修课依赖关系的前提下，能获得的最大总学分。
- 问题本质与解题思路：教科书级的树形背包。每门课的学分就是价值，体积统一为 1，总容量就是选课数 $N$。
- 核心思路：由于课程关系可能构成多棵树（即有多个先修课为 0 的独立课程），直接套用上文模板中的超级根节点技术。将 0 号节点作为所有无先修课课程的共同父亲。因为引入了虚拟节点 0，原本选 $N$ 门课的总容量限制，在代码里需要映射为选 $N+1$ 个物品（包括 0 号虚拟物品）。调用
dfs(0, -1)后，输出f[0][N + 1]即可直通 AC。
2. 洛谷 P1273 有线电视网
- 题意描述：一个有线电视网由多个转发站和终端用户构成，结构呈一棵树。已知每个终端用户愿意支付一定的看球赛费用。而每条传输线（树枝）都有一定的准备维护成本。电视网的根节点负责发射信号。求在电视网不亏本（即用户付的总费用 $ ge$ 传输线总成本）的前提下，最多能让多少个终端用户看到球赛。
- 问题本质与解题思路：状态维度置换的树形背包。如果以“成本”作为背包容量，由于成本数据范围极大，会导致状态网格爆炸。我们需要执行维度置换：将“用户数量”作为背包的容量轴。
- 状态设计：设 $f[u][j]$ 表示以 $u$ 为根的子树中，让 $j$ 个用户看到球赛时，电视网所能获得的最大净收益（总收入 - 总成本）。
- 转移方程：
$$f[u][j] = \max \left( f[u][j], f[u][j - k] + f[v][k] - \text{cost}(u, v) \right)$$
在 DFS 回溯时，父节点通过组合子树的用户数 $k$ 来刷表。最终，在根节点 $root$ 的状态轴上，从大到小搜寻第一个满足 $f[root][j] \ge 0$ 的下划线 $j$，该 $j$ 即为最多能保留的用户数。此题完美展示了背包问题中“体积与价值维数互换”的高阶技巧。