树上综合问题
本节目标
组合子树汇合、树形 DP、前缀和、编码、位置编号与父节点映射，处理树上综合模型。
第七章公共示例树
根 1，左右孩子 2、3，节点 2 的左右孩子为 4、5。
1
/ \
2 3
/ \
4 5
前四栏已经分别练习了遍历、子树报告、路径状态和结构构造。本栏不再寻找一个覆盖所有树题的万能模板，而是把这些基础模型与新的状态组合：答案可能在左右信息汇合处出现，可能需要同时维护向上贡献和全局最优，也可能要给节点补上位置或父节点关系。
识别信号
- 两个目标的信息从左右子树返回，并在某个节点首次汇合；
- 当前节点能组成完整答案，但父节点只能使用其中一条分支；
- 根到当前节点的前缀差能表示一条向下路径的计数；
- 需要把树编码为字符串后无歧义地恢复原结构；
- 层序遍历中的宽度由空位间的位置跨度决定；
- 搜索要从目标向父节点移动，原有父子方向不足以表达状态转移。
问题模型与核心不变量
公共树上，节点 2 向上报告的单边最大贡献为 7（路径 2 → 5）；根 1 则可把它与节点 3 的贡献合并，得到路径 5 → 2 → 1 → 3 的和 11。这区分了“向上报告的状态”和“当前节点可形成的完整答案”。
先判断信息怎样流动。最近公共祖先让左右子树报告目标节点，两个非空报告在当前节点汇合；最大路径和向上只返回单边贡献，父节点只接纳其中的非负部分，而当前节点可以组合左右贡献。路径总和 III 的前缀计数只对当前根到节点的路径有效，离开节点时必须撤销。
序列化协议必须同时保存节点值、访问顺序和空节点，否则不同结构可能得到同一串文本。最大宽度把节点看作完全二叉树中的位置：每层以首位置归一化，既保持跨度又避免编号无意义增长。距离为 K 则先建立 child -> parent 映射，把树转换成可双向移动的无向状态图，并按节点身份去重。
通用模板
先问：答案由子树信息汇合得到吗？
→ 是否要区分“向上返回值”和“当前节点的完整答案”？
→ 路径计数能否改写为两个前缀和的差？
→ 编码时是否保留了值、顺序和空节点？
→ 层序队列是否还要携带位置状态？
→ 是否需要把父子关系补成双向邻接关系？
这些问题决定状态，而不是决定递归或 BFS 的表面写法。若只是让子树向父节点报告单一信息，先回顾子树信息与递归判断；本栏只保留那些需要额外状态或不同信息流向的组合题。
模板变体
- LCA 返回节点或空，左右都非空时当前节点成为答案。
- 最大路径和向上返回一侧最大贡献，在当前节点用左右贡献更新全局答案。
- 前缀和计数在进入节点时登记、离开节点时撤销，保证兄弟子树互不污染。
- 前序编码用
#表示空节点，反序列化按同一 token 顺序消费。 - 宽度 BFS 队列保存
(node, index)，每层先减去首个编号。 - 距离搜索在父节点映射建好后从目标 BFS，入队时立即标记访问。
母题序列
按拓展顺序练习：
- 二叉树的最近公共祖先（拓展）：让两侧子树报告目标节点，在首次汇合处得到答案。
- 二叉树中的最大路径和（拓展）：区分可向上延伸的单边贡献和经过当前节点的完整路径。
- 路径总和 III（拓展）：用前缀和差计数，并成对维护登记与撤销。
- 二叉树的序列化与反序列化（拓展）：定义包含空节点的前序协议，往返重建结构。
- 二叉树最大宽度（拓展）：按完全二叉树位置计算一层两端的跨度。
- 二叉树中所有距离为 K 的结点（拓展）：补上父节点边后，从目标向外按层搜索。
常见误区
- 把当前节点的完整路径直接返回给父节点，拼出并不连续的路径。
- 前缀计数没有在回程撤销，令一个分支的状态误计入兄弟分支。
- 序列化省略空节点，导致不同结构无法区分。
- 把一层实际节点数当作最大宽度，忽略中间空位。
- 位置编号持续从根累乘，深树中产生不必要的大数。
- 只沿孩子搜索距离为 K 的节点，遗漏必须先向父节点移动的路径。
- 用节点值代替节点身份，重复值时把不同节点错误合并。
迁移方向
遇到新的树题，先明确它缺少的是哪一种信息：向上汇总、沿路径维护、结构编码、位置坐标还是反向边。更复杂的树形 DP、倍增 LCA、树链剖分和树上数据结构需要新的模型，不应从这六题机械外推。