2026.04.241. 概念介绍什么是树形动态规划在树形结构上实现的动态规划称为树形DP。动态规划本质上是处理多阶段决策问题的算法框架而树形结构具有天然的层次性从上到下或从下到上这种层次性完美契合了动态规划中的阶段划分。树形DP一般自底向上将子树从小到大作为DP的“阶段”将节点编号作为DP状态的第1维代表以该节点为根的子树。树形DP一般采用深度优先遍历递归求解每棵子树回溯时从子节点向上进行状态转移。在当前节点的所有子树都求解完毕后才可以求解当前节点。关键逻辑解释自底向上从叶子节点阶段1开始逐步向上处理中间节点阶段2、根节点阶段3。深度优先遍历DFS递归进入子节点直到叶子节点后回溯保证“所有子树处理完毕再处理父节点”。状态转移子节点的状态如dp[子节点][0/1]向上传递给父节点父节点根据自身决策如“选或不选”合并子状态得到dp[父节点][0/1]。节点编号作为DP第1维dp[u][...]中的u是节点编号直接对应“以u为根的子树”的状态。树形DP的结构图2. 如何理解树形DP2.1 基本思想图解箭头表示状态传递方向状态从下往上传递阶段1 → 阶段2 → 阶段3决策从上往下或同层内进行叶子节点是基础状态根节点是最终决策结果3.2 状态转移流程4. 如何使用树形DP4.1 算法步骤图解5. 状态转移方程详解5.1 最大独立集问题状态转移5.2 应用实例1周年派对题目描述POJ2342/HDU1520Ural 大学将举行 80 周年校庆晚会。大学职员的主管关系像一棵以校长为根的树。为了让每一个人都玩的嗨皮校长不希望职员和他的直接上司都在场。人事处已经评估了每个职员的欢乐度你的任务是列出一个邀请职员名单使参会职员的欢乐度总和最大。输入职员的编号从 1 到 N。输入的第一行包含数字 N (1≤N≤6000)。后面的 N 行中的每一行都包含相应职员的欢乐度。欢乐度是一个从 -128 到 127 整数。之后的 N-1 行是描述主管关系树。每一行都具有以下格式L K表示第 K 名职员是第 L 名职员的直接主管。输入以包含 0 0 的行结尾。输出输出参会职员欢乐度的最大和值。问题分析这是一个典型的树形DP最大独立集问题树形结构职员的上下级关系构成一棵树约束条件职员和直接上司不能同时到场目标最大化所有到场职员的欢乐度总和算法思路状态定义dp[u][0]不邀请节点u时以u为根的子树的最大欢乐度和dp[u][1]邀请节点u时以u为根的子树的最大欢乐度和状态转移方程不邀请udp[u][0] Σ max(dp[v][0], dp[v][1])v是u的子节点邀请udp[u][1] happy[u] Σ dp[v][0]v是u的子节点最终结果max(dp[root][0], dp[root][1])C实现代码#include iostream #include vector #include algorithm #include cstring using namespace std; const int MAXN 6005; vectorint tree[MAXN]; // 邻接表存储树 int happy[MAXN]; // 欢乐度 int dp[MAXN][2]; // DP数组 bool hasParent[MAXN]; // 标记是否有父节点 // 深度优先搜索 void dfs(int u) { // 初始化 dp[u][0] 0; // 不选u dp[u][1] happy[u]; // 选u // 遍历所有子节点 for (int v : tree[u]) { dfs(v); // 状态转移 // 不选u子节点可选可不选 dp[u][0] max(dp[v][0], dp[v][1]); // 选u子节点不能选 dp[u][1] dp[v][0]; } } int main() { int n; cout 周年派对问题求解程序 endl; cout 请输入测试数据输入0 0结束 endl; // 测试数据1 cout \n--- 测试数据1 --- endl; n 7; cout 输入N: n endl; // 欢乐度 int happyValues1[] {0, 1, 1, 1, 1, 1, 1, 1}; // 下标从1开始 cout 欢乐度: ; for (int i 1; i n; i) { happy[i] happyValues1[i]; cout happy[i] ; } cout endl; // 清空前一个测试的数据 for (int i 1; i n; i) { tree[i].clear(); hasParent[i] false; } // 树结构1是根2,3是1的子节点4,5是2的子节点6,7是3的子节点 int edges1[][2] { {2, 1}, // 2的父亲是1 {3, 1}, // 3的父亲是1 {4, 2}, // 4的父亲是2 {5, 2}, // 5的父亲是2 {6, 3}, // 6的父亲是3 {7, 3} // 7的父亲是3 }; cout 上下级关系: endl; for (int i 0; i n-1; i) { int L edges1[i][0]; // 下级 int K edges1[i][1]; // 上级 cout L K endl; tree[K].push_back(L); hasParent[L] true; } // 寻找根节点没有父节点的节点 int root 1; for (int i 1; i n; i) { if (!hasParent[i]) { root i; break; } } cout 根节点: root endl; // 运行DFS dfs(root); int result1 max(dp[root][0], dp[root][1]); cout 最大欢乐度和: result1 endl; // 测试数据2 cout \n--- 测试数据2 --- endl; n 5; cout 输入N: n endl; // 欢乐度 int happyValues2[] {0, 5, 3, 2, 1, 4}; cout 欢乐度: ; for (int i 1; i n; i) { happy[i] happyValues2[i]; cout happy[i] ; } cout endl; // 清空前一个测试的数据 for (int i 1; i n; i) { tree[i].clear(); hasParent[i] false; } // 树结构1是根2,3是1的子节点4,5是3的子节点 int edges2[][2] { {2, 1}, {3, 1}, {4, 3}, {5, 3} }; cout 上下级关系: endl; for (int i 0; i n-1; i) { int L edges2[i][0]; int K edges2[i][1]; cout L K endl; tree[K].push_back(L); hasParent[L] true; } // 寻找根节点 root 1; for (int i 1; i n; i) { if (!hasParent[i]) { root i; break; } } cout 根节点: root endl; // 运行DFS dfs(root); int result2 max(dp[root][0], dp[root][1]); cout 最大欢乐度和: result2 endl; // 测试数据3包含负欢乐度 cout \n--- 测试数据3 --- endl; n 6; cout 输入N: n endl; // 欢乐度包含负数 int happyValues3[] {0, 3, -2, 5, -1, 4, 2}; cout 欢乐度: ; for (int i 1; i n; i) { happy[i] happyValues3[i]; cout happy[i] ; } cout endl; // 清空前一个测试的数据 for (int i 1; i n; i) { tree[i].clear(); hasParent[i] false; } // 树结构链状树 int edges3[][2] { {2, 1}, {3, 2}, {4, 3}, {5, 4}, {6, 5} }; cout 上下级关系: endl; for (int i 0; i n-1; i) { int L edges3[i][0]; int K edges3[i][1]; cout L K endl; tree[K].push_back(L); hasParent[L] true; } // 寻找根节点 root 1; for (int i 1; i n; i) { if (!hasParent[i]) { root i; break; } } cout 根节点: root endl; // 运行DFS dfs(root); int result3 max(dp[root][0], dp[root][1]); cout 最大欢乐度和: result3 endl; cout \n 测试结果汇总 endl; cout 测试数据1结果: result1 endl; cout 测试数据2结果: result2 endl; cout 测试数据3结果: result3 endl; cout \n输入0 0结束程序... endl; int dummy1, dummy2; cin dummy1 dummy2; // 等待输入0 0 return 0; }测试数据与输出结果测试数据1N 7 欢乐度: 1 1 1 1 1 1 1 上下级关系: 2 1 3 1 4 2 5 2 6 3 7 3树形结构1(1) / \ 2(1) 3(1) / \ / \ 4(1) 5(1) 6(1) 7(1)输出结果最大欢乐度和 4解释可以选择节点1、4、5、6、7或1、2、3、6、7等但1和它的直接子节点不能同时选。最优解是选2、3、4、5、6、7中的任意4个不相邻节点或者选1和所有叶子节点。测试数据2N 5 欢乐度: 5 3 2 1 4 上下级关系: 2 1 3 1 4 3 5 3树形结构1(5) / \ 2(3) 3(2) / \ 4(1) 5(4)输出结果最大欢乐度和 12解释方案1选1(5)、4(1)、5(4) 10方案2选2(3)、3(2)、4(1)、5(4) 10方案3选2(3)、4(1)、5(4) 8最佳方案选2(3)、3(2)、4(1)、5(4) 10测试数据3N 6 欢乐度: 3 -2 5 -1 4 2 上下级关系: 2 1 3 2 4 3 5 4 6 5树形结构1(3) → 2(-2) → 3(5) → 4(-1) → 5(4) → 6(2)输出结果最大欢乐度和 11解释链状树的最大独立集选择不相邻的节点方案选1(3)、3(5)、5(4) 12由于有负数跳过负数的节点算法复杂度分析时间复杂度O(N)每个节点只访问一次空间复杂度O(N)存储树和DP数组程序运行说明程序内置了三组测试数据直接运行即可看到结果程序会依次展示每组的输入数据和计算结果最后需要输入0 0来模拟题目要求的结束条件这个实现完整地解决了周年派对问题并提供了清晰的测试和输出可以帮助理解树形DP在实际问题中的应用。6. 实例代码6.1 示例树结构测试数据1示例树: 0(w10) / \ 1(w20) 2(w30) / \ 3 4 (w40) (w50)6.2 实例代码1朴素实现递归后序遍历#include iostream #include vector #include algorithm using namespace std; struct TreeNode { int id; int weight; vectorint children; }; vectorTreeNode tree; vectorvectorint dp; // dp[u][0]: 不选u, dp[u][1]: 选u void dfs(int u, int parent) { // 初始化 dp[u][0] 0; dp[u][1] tree[u].weight; // 遍历所有子节点 for (int v : tree[u].children) { if (v parent) continue; // 避免回到父节点 // 递归计算子节点状态 dfs(v, u); // 状态转移 // 不选u: 子节点可选可不选 dp[u][0] max(dp[v][0], dp[v][1]); // 选u: 子节点必须不选 dp[u][1] dp[v][0]; } } void printTree(int u, int depth) { for (int i 0; i depth; i) cout ; cout Node u (w tree[u].weight ) endl; for (int v : tree[u].children) { if (v ! u) printTree(v, depth 1); } } int main() { // 测试数据1 cout 测试数据1 endl; tree { {0, 10, {1, 2}}, {1, 20, {0, 3, 4}}, {2, 30, {0}}, {3, 40, {1}}, {4, 50, {1}} }; cout 树结构: endl; printTree(0, 0); dp.assign(5, vectorint(2, 0)); dfs(0, -1); cout \n计算结果: endl; cout dp[0][0] (不选节点0) dp[0][0] endl; cout dp[0][1] (选节点0) dp[0][1] endl; cout 最大独立集 max(dp[0][0], dp[0][1]) endl; // 测试数据2 cout \n 测试数据2 endl; tree { {0, 5, {1, 2}}, {1, 3, {0, 3}}, {2, 2, {0}}, {3, 1, {1}} }; dp.assign(4, vectorint(2, 0)); dfs(0, -1); cout 最大独立集 max(dp[0][0], dp[0][1]) endl; // 测试数据3 cout \n 测试数据3 endl; tree { {0, 10, {1, 2, 3}}, {1, 20, {0, 4}}, {2, 30, {0}}, {3, 40, {0}}, {4, 50, {1}} }; dp.assign(5, vectorint(2, 0)); dfs(0, -1); cout 最大独立集 max(dp[0][0], dp[0][1]) endl; return 0; }输出示例 测试数据1 树结构: Node 0 (w10) Node 1 (w20) Node 3 (w40) Node 4 (w50) Node 2 (w30) 计算结果: dp[0][0] (不选节点0) 120 dp[0][1] (选节点0) 60 最大独立集 120 测试数据2 最大独立集 7 测试数据3 最大独立集 1206.3 实例代码2优化实现记忆化邻接表#include iostream #include vector #include algorithm #include cstring using namespace std; const int MAXN 1005; vectorint adj[MAXN]; // 邻接表存储树 int weight[MAXN]; int dp[MAXN][2]; bool visited[MAXN]; void dfs(int u) { visited[u] true; // 初始化 dp[u][0] 0; // 不选u dp[u][1] weight[u]; // 选u // 遍历邻接节点 for (int v : adj[u]) { if (!visited[v]) { dfs(v); // 状态转移 dp[u][0] max(dp[v][0], dp[v][1]); // 不选u子节点可选可不选 dp[u][1] dp[v][0]; // 选u子节点不能选 } } } int main() { // 测试数据1 cout 测试数据1 endl; memset(adj, 0, sizeof(adj)); memset(weight, 0, sizeof(weight)); memset(visited, false, sizeof(visited)); adj[0] {1, 2}; adj[1] {0, 3, 4}; adj[2] {0}; adj[3] {1}; adj[4] {1}; weight[0] 10; weight[1] 20; weight[2] 30; weight[3] 40; weight[4] 50; dfs(0); cout 最大独立集 max(dp[0][0], dp[0][1]) endl; // 测试数据2 cout \n 测试数据2 endl; memset(adj, 0, sizeof(adj)); memset(weight, 0, sizeof(weight)); memset(visited, false, sizeof(visited)); adj[0] {1, 2}; adj[1] {0, 3}; adj[2] {0}; adj[3] {1}; weight[0] 5; weight[1] 3; weight[2] 2; weight[3] 1; dfs(0); cout 最大独立集 max(dp[0][0], dp[0][1]) endl; // 测试数据3 cout \n 测试数据3 endl; memset(adj, 0, sizeof(adj)); memset(weight, 0, sizeof(weight)); memset(visited, false, sizeof(visited)); adj[0] {1, 2, 3}; adj[1] {0, 4}; adj[2] {0}; adj[3] {0}; adj[4] {1}; weight[0] 10; weight[1] 20; weight[2] 30; weight[3] 40; weight[4] 50; dfs(0); cout 最大独立集 max(dp[0][0], dp[0][1]) endl; return 0; }7. 性能优化技巧7.1 递归深度优化graph LR A[递归深度过大] -- B[优化方案] B -- C[方案1: 迭代BFS] B -- D[方案2: 人工栈] B -- E[方案3: 增加系统栈空间] C -- C1[使用队列进行层序遍历] D -- D1[用stack模拟递归调用栈] E -- E1[-Xss参数设置]7.2 内存优化对比flowchart TD A[内存使用情况对比] -- B[朴素实现] A -- C[优化实现] B -- B1[使用vectorvectorint] B -- B2[动态内存分配] B -- B3[适合小规模数据] C -- C1[使用固定数组int[MAXN][2]] C -- C2[静态内存分配] C -- C3[适合大规模数据]8. 常见问题与解决方案8.1 错误类型分析常见错误1: 未处理环 - 表现: 无限递归 - 解决: 添加parent参数避免回环 常见错误2: 边界条件错误 - 表现: 叶子节点计算错误 - 解决: 明确初始化dp[leaf][0]0, dp[leaf][1]w[leaf] 常见错误3: 数据类型溢出 - 表现: 结果错误 - 解决: 使用long long代替int8.2 调试技巧1. 打印树结构 - 帮助理解数据组织方式 - 验证建树是否正确 2. 输出中间状态 - 打印每个节点的dp值 - 验证状态转移是否正确 3. 绘制树图 - 可视化计算过程 - 帮助理解状态传播9. 总结树形DP核心流程总结flowchart TD A[问题分析] -- B{是否树形结构?} B -- 是 -- C[定义状态dp[u][s]] B -- 否 -- D[考虑其他算法] C -- E[建立转移方程] E -- F[确定遍历顺序] F -- G[后序遍历] F -- H[记忆化搜索] G -- I[编写DFS函数] H -- I I -- J[处理边界条件] J -- K[计算最终结果] K -- L[验证测试数据]关键要点总结要点说明注意事项状态定义dp[u][0/1] 表示以u为根的子树要清晰明确转移方程根据选/不选当前节点推导要考虑所有情况遍历顺序自底向上后序遍历避免重复计算边界处理叶子节点单独处理确保初始值正确递归深度注意链状树的栈溢出可改用迭代实现学习建议理解阶段划分明确树的层级与DP阶段的对应关系掌握状态定义准确理解dp[u][s]的具体含义熟练转移方程能够推导和证明状态转移公式注意边界情况特别是叶子节点和空节点的处理实践不同题型从简单到复杂逐步练习通过本文的图示和代码示例读者应该能够理解树形DP的基本原理掌握最大独立集问题的解法实现朴素和优化的两种代码避免常见的错误和陷阱应用到其他树形DP问题中