第7章笔记：树上算法

目标

利用树的唯一路径和层级结构，把全局询问压成局部合并。

七课依赖

• 树的遍历与子树大小：围绕树的遍历与子树大小先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 树的直径：围绕树的直径先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 倍增LCA：围绕倍增LCA先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 欧拉序与子树区间：围绕欧拉序与子树区间先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 树上差分：围绕树上差分先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 重链剖分入口：围绕重链剖分入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 树形DP的依赖方向：围绕树形DP的依赖方向先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
树的遍历与子树大小	围绕树的遍历与子树大小先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
树的直径	围绕树的直径先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
倍增LCA	围绕倍增LCA先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
欧拉序与子树区间	围绕欧拉序与子树区间先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
树上差分	围绕树上差分先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
重链剖分入口	围绕重链剖分入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
树形DP的依赖方向	围绕树形DP的依赖方向先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	根会改变父子关系但不改变无根距离；递归深度可能爆栈。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。