树形 DP 入门：递归返回值要先想清楚
一、树题难在状态方向
树形 DP 常让人头疼，不是因为代码一定很长，而是因为状态方向容易乱。一个节点要从子节点拿什么信息？返回给父节点什么？答案是在子树里更新，还是在根节点统一得到？这些问题没想清楚，递归就会写成一团。
树形 DP 的第一步，是定义递归返回值。
二、先画信息流
flowchart TD A[叶子节点] --> B[返回基础状态] B --> C[父节点合并子状态] C --> D[更新当前状态] D --> E[返回给更高层]树的天然结构适合后序遍历：先处理子节点，再合并到父节点。大多数树形 DP 都是在这个方向上工作。
tree_dp_questions: return_meaning: required merge_children: required update_global_answer: optional base_case: required写代码前先回答这四个问题，能少很多返工。
三、例子：二叉树最大路径和
def max_path_sum(root): ans = float("-inf") def dfs(node): nonlocal ans if not node: return 0 left = max(dfs(node.left), 0) right = max(dfs(node.right), 0) ans = max(ans, node.val + left + right) return node.val + max(left, right) dfs(root) return ans这里dfs(node)返回的是：从当前节点向父节点延伸时，能提供的最大单边路径和。为什么只能返回单边？因为父节点如果继续连接，路径不能在当前节点分叉后再往上走。
但全局答案可以用左右两边同时更新：node.val + left + right。返回值和答案更新含义不同，这是树形 DP 最常见的关键点。
四、不要把全局答案和返回值混在一起
有些题返回值就是答案，有些题需要全局变量。判断标准是：父节点是否能直接使用这个值。如果某个值只在当前子树内部成立，不能向父节点延伸，就不要当返回值。
def dfs(node): # return 给父节点的信息 # update 当前子树内部答案 pass写注释时明确这两层含义，比写复杂变量名更有用。
还要注意空节点的返回值。空节点返回 0、-inf、None，取决于状态定义。不要因为模板里常写 0，就所有题都写 0。
最后，树形 DP 的复杂度通常是 O(n)，因为每个节点只处理一次。但如果每个节点合并子树时又扫描子树，就会变成 O(n²)。合并成本也要算进去。
多叉树题还要注意合并顺序。二叉树只有左右两个子节点，状态合并容易写；多叉树如果要选若干子树、统计前 k 个结果，就可能变成背包式合并。此时每个节点的合并成本不一定是 O(度数)。
tree_dp_merge_check: binary_tree: simple_merge multi_child_tree: consider_knapsack_merge rerooting: require_parent_contribution还有一类换根 DP，需要同时考虑子树贡献和父方向贡献。普通后序返回值不够，需要一次自底向上、一次自顶向下。看到“每个节点作为根的答案”时，就要警惕这种模式。
五、总结
树形 DP 入门要先定义递归返回值、子状态合并方式、全局答案更新位置和空节点边界。
递归返回值想清楚，代码自然会短。没想清楚，树再简单也会绕晕。
