核心逻辑与数学原理
树形动态规划（Tree DP）是一种将动态规划的阶段推进建立在树状拓扑结构（有向无环图）上的算法模型。其核心本质在于利用后序遍历（DFS）的天然拓扑序，实现状态从子节点向父节点的线性能量传导。
1. 拓扑序的几何特化
在线性 DP 中，阶段沿着一维轴（如下标 $i$）有序推进。而在树形结构中，一个父节点 $u$ 的最优决策依赖于其所有子节点 $v \\in ext{son}(u)$ 固化后的状态。由于树没有环，我们可以通过一次深度优先搜索（DFS），在递归回溯（即后序遍历位置）时收集子节点信息。此时，子节点的生命周期已经结束，其状态已是最优解，完美满足无后序性。
2. 没有上司的舞会（经典最大独立集模型）
给定一棵建立有父子关系的树，每个节点都有一个快乐值。现需选出一个节点子集，使得任意有边相连的两个节点（即父子关系）不能同时被选中。求该子集的最大快乐值之和。
-
决策冲突的离散化：对于任意节点 $u$，其核心决策只有两种：
- 选 $u$：一旦选了 $u$，为了不违反规则，其所有直接子节点 $v$ 绝对不能选。
- 不选 $u$：如果不选 $u$，其子节点 $v$ 摆脱了父节点的束缚，可选可不选（哪个分支利益最大就选哪个）。
-
状态的维度解析：通过引入一个二维状态 $f[u][0/1]$，将复杂的全局互斥冲突在局部父子节点之间进行了解耦，从而将指数级的搜索空间压缩为 $O(N)$ 的线性网格。
状态设计与算法推导
1. 状态空间定义
设 $f[u][0]$ 表示在以 $u$ 为根的子树中，不选择节点 $u$ 时所能获得的最大快乐值。 设 $f[u][1]$ 表示在以 $u$ 为根的子树中，选择节点 $u$ 时所能获得的最大快乐值。
2. 状态转移方程推导
对于节点 $u$，设其子节点集合为 $ ext{son}(u)$，当前节点的原始快乐值为 $R[u]$：
- 当选择节点 $u$ 时：所有的子节点 $v$ 都被强制剥夺了被选中的资格，只能从不选 $v$ 的状态转移而来。
$$f[u][1] = R[u] + \sum_{v \\in \text{son}(u)} f[v][0]$$
- 当不选择节点 $u$ 时：每一个子节点 $v$ 都可以自由选择“选”或“不选”，为了保证总和最大，局部采用全局最优策略。
$$f[u][0] = \sum_{v \\in \text{son}(u)} \max(f[v][0], f[v][1])$$
3. 边界条件
当 $u$ 为叶子节点（$ ext{son}(u) = \emptyset$）时：
$$f[u][0] = 0, \quad f[u][1] = R[u]$$
该边界在 DFS 回溯触底时自然激活。
C++ 标准源码（NOIP风格）
以下源码为“没有上司的舞会”考场标准实现。采用高性能邻接表（std::vector）建树，严格兼容 Linux g++ -O2 编译规范。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 6005;
int r[MAXN]; // 存储每个节点的快乐值
int f[MAXN][2]; // f[u][0]: 不选u, f[u][1]: 选u
bool has_parent[MAXN];// 标记是否有父节点，用于寻找整棵树的根节点
vector<int> tree[MAXN];// 邻接表建树
// 树形 DP 核心：利用 DFS 回溯实现自底向上的状态转移
void dfs(int u) {
// 1. 初始化叶子节点的基本元状态
f[u][0] = 0;
f[u][1] = r[u];
// 2. 纵向向下拓扑推进
for (int v : tree[u]) {
dfs(v); // 先让子节点去计算它们自己的子树状态
// 3. 回溯时利用子节点状态更新父节点（自底向上贡献）
f[u][1] += f[v][0]; // 选了 u，子节点 v 强制不能选
f[u][0] += max(f[v][0], f[v][1]); // 不选 u，子节点 v 怎么大怎么来
}
}
int main() {
// 优化 I/O 性能
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; ++i) {
cin >> r[i];
}
// 读入关系，建立有向树（从父节点指向子节点）
for (int i = 1; i < n; ++i) {
int l, k; // l 是 k 的直接下属（l 是子节点，k 是父节点）
cin >> l >> k;
tree[k].push_back(l);
has_parent[l] = true; // 标记 l 有父亲
}
// 寻找整棵树的几何根节点（没有父亲的节点就是根）
int root = 1;
while (has_parent[root]) {
root++;
}
// 从根节点启动 DFS 状态网络交织
dfs(root);
// 全局最优解必然在“选根”与“不选根”两种终态中产生
cout << max(f[root][0], f[root][1]) << "\n";
return 0;
}NOIP 实战避坑指南
1. 无向图建树未跳过父节点导致死循环爆栈
- 现象：有些题目给出的树边是无向的（如 $u$ 与 $v$ 相连，没说谁是谁父亲）。选手如果直接加双向边
tree[u].push_back(v); tree[v].push_back(u);且在 DFS 中写for(int v : tree[u]) dfs(v);，会导致 DFS 在父子节点之间反复横跳，瞬间引发段错误（Segmentation Fault / 栈溢出）。 - 规避手段：对于无向边建树，DFS 函数必须多传一个参数记录当前节点的父亲：
void dfs(int u, int fa)。在遍历子节点循环中，强制加上安全哨兵：if (v == fa) continue;。
2. 根节点定位错误
- 现象：默认节点 $1$ 就是整棵树的根，直接调用
dfs(1)。这在很多题目中是致命的，因为数字编号是随机的，节点 $1$ 极有可能只是某个末端叶子节点。从它开始搜，不仅漏掉大片子树，还会导致状态逻辑南辕北辙。 - 规避手段：利用入度数组或布尔标记数组
has_parent记录每个节点的依赖关系。读入完所有边后，必须强制遍历一次，找出那个“入度为 0 / 没有父亲”的节点作为真正的 DFS 起点。
经典 NOIP/洛谷 真题
1. 洛谷 P1352 没有上司的舞会
- 题意描述：即上文详解的教科书级模型。
- 问题本质与解题思路：标准的树形最大独立集问题。核心在于二维状态 $f[u][0/1]$ 的解耦设计。通过 $O(N)$ 复杂度的单次 DFS 即可完美收官。
2. 洛谷 P2015 二叉苹果树
- 题意描述：有一棵二叉苹果树，每条树枝上长有若干个苹果。由于清理需要，必须剪掉一些树枝，使最终保留的树枝总数恰好为 $Q$ 条。已知树根是不允许被剪掉的。求保留 $Q$ 条树枝的前提下，最多能留住多少个苹果。
- 问题本质与解题思路：树形背包（树上带权有赖背包）模型。
- 状态设计：设 $f[u][j]$ 表示以 $u$ 为根的子树中，保留 $j$ 条树枝所能获得的最大苹果数。
- 核心思路：在 DFS 回溯时，父节点 $u$ 的背包容量 $j$ 需要分配给左子树和右子树。对于子节点 $v$，如果分给它 $k$ 条树枝，由于连接 $u$ 和 $v$ 的这条树枝本身必须保留（消耗 1 个容量），所以 $v$ 的子树实际可用容量为 $k-1$。通过在父节点内部嵌套一层类似于分组背包的容量枚举：
$$f[u][j] = \max_{v \\in \text{son}(u)} \{ f[u][j - k] + f[v][k - 1] + \text{apple}(u, v) \}$$
该模型完美将树形结构与动态规划的容量背包融合在一起。