竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1树的遍历与子树大小

闭卷重建树的遍历与子树大小的对象、状态、事件、不变量与一个失败反例。

2树的直径

闭卷重建树的直径的对象、状态、事件、不变量与一个失败反例。

3倍增LCA

闭卷重建倍增LCA的对象、状态、事件、不变量与一个失败反例。

4欧拉序与子树区间

闭卷重建欧拉序与子树区间的对象、状态、事件、不变量与一个失败反例。

5树上差分

闭卷重建树上差分的对象、状态、事件、不变量与一个失败反例。

6重链剖分入口

闭卷重建重链剖分入口的对象、状态、事件、不变量与一个失败反例。

7树形DP的依赖方向

闭卷重建树形DP的依赖方向的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕树的直径先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成树的直径的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕树的遍历与子树大小先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成树的遍历与子树大小的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕欧拉序与子树区间先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成欧拉序与子树区间的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕倍增LCA先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成倍增LCA的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕重链剖分入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成重链剖分入口的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕树上差分先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成树上差分的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕树形DP的依赖方向先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成树形DP的依赖方向的暴力、优化、对拍与复盘；边界：根会改变父子关系但不改变无根距离；递归深度可能爆栈。本课必须再检查边界输入、整数溢出、下标和不可行状态。。