最大层内元素和 (Maximum Level Sum of a Binary Tree)

1. 题目描述

题目背景： 在二叉树的层级分析中，除了求每一层的最大值或平均值，有时我们需要找到“贡献度”最高的一层。本题要求在给定的二叉树中，计算哪一层的节点权值之和最大。

任务描述： 给定一棵拥有 $n$ 个节点的二叉树，根节点位于第 $1$ 层，其子节点位于第 $2$ 层，依此类推。 请找出层内元素之和 最大 的那层，并返回其层号。如果有多个层号对应的元素之和相同，则返回层号 最小 的那个。

输入格式：

1. 第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示节点总数。
2. 接下来的 $n$ 行，每行包含三个整数 $v_i, l_i, r_i$：
   • $v_i$ 为第 $i$ 个节点的权值 ($-10^5 \le v_i \le 10^5$)。
   • $l_i$ 为左孩子编号。
   • $r_i$ 为右孩子编号。
3. 节点编号从 $1$ 到 $n$。如果孩子不存在，则编号为 $0$。根节点固定为编号 $1$。

输出格式： 一个整数，表示和最大的最小层号。

样例 1： 输入：

5
1 2 3
7 4 5
0 0 0
7 0 0
-8 0 0

输出：

2

(解释：第 1 层和为 1；第 2 层和为 7 + 0 = 7；第 3 层和为 7 + (-8) = -1。最大和出现在第 2 层)

样例 2： 输入：

7
989 2 3
10250 4 5
98693 0 0
-32127 0 0
0 0 0
-19109 0 0
-32127 0 7

输出：

2

2. 预备知识点

1. 二叉树存储：结构体数组（静态建树）。
2. 层序遍历 (BFS)：最适合处理层级累加问题。
3. 极值维护：
   • 最大和初始化：由于权值可能为负，最大和应初始化为极小值（如 -2e18）。
   • 层号维护：在遍历过程中同步维护当前层号和最优层号。
4. 数据类型：虽然权值是 int，但单层和可能达到 $10^4 \times 10^5 = 10^9$，建议累加器使用 long long 以防万一。

3. 启发式思维引导

第一步：分层思维

请在草稿纸上把二叉树画出来，并在每一层旁边写下它们的和。

• 思考：当你计算第 $k$ 层的和时，你是否需要知道第 $k+1$ 层的信息？
• 结论：不需要。这意味着我们可以按层处理，处理完一层后立即更新全局最大值。

第二步：如何打破“平局”

题目要求：“如果和相同，返回最小层号”。

• 技巧：在比较大小时，使用 if (current_sum > max_sum) 而不是 >=。因为我们是从第 1 层向后遍历的，只有遇到严格更大的和时才更新层号，这样就能保证保留的是最小的层号。

第三步：初值陷阱

• 危险操作：把 maxSum 初始化为 0。
• 分析：如果整棵树的节点权值全是负数，那么最大的层和也是负数（比如 -5）。如果你初始化为 0，程序会错误地认为最大和是 0。
• 正确做法：初始化为 LLONG_MIN 或第一层的和。

4. 算法流程图 (基于 BFS 策略)

graph TD
    Start(开始) --> Init[初始化队列 Q 并将根节点 1 入队]
    Init --> State[初始化 maxSum 为极小值, maxLevel 为 1, curLevel 为 1]
    
    State --> WhileQ{队列 Q 是否不为空}
    WhileQ -- 否 --> EndOutput[输出 maxLevel 并结束]
    
    WhileQ -- 是 --> LevelProc[获取当前层大小 sz, 初始化 levelSum 为 0]
    LevelProc --> ForLoop{循环 sz 次}
    
    ForLoop -- 迭代中 --> PopNode(弹出队首节点 u)
    PopNode --> AddSum(将 u 的权值加到 levelSum)
    AddSum --> ChildCheck{将 u 的左右子节点入队}
    ChildCheck --> ForLoop
    
    ForLoop -- 结束 --> Compare{levelSum 是否大于 maxSum}
    Compare -- 是 --> Update[更新 maxSum 为 levelSum, maxLevel 为 curLevel]
    Compare -- 否 --> NextLevel[curLevel 自增 1]
    Update --> NextLevel
    NextLevel --> WhileQ

5. 读题关键词总结

在 NOI 读题时，以下词汇是解题钥匙：

1. “层内元素之和” (Level Sum)：

   • 指示：必须进行层序遍历。BFS 的 sz = q.size() 模板是处理此类问题的标准武器。

2. “最大” (Maximum)：

   • 警示：注意初值。权值包含负数时，不能以 0 为基准。

3. “层号最小” (Smallest Level Index)：

   • 指示：更新策略。遍历方向是从小到大，因此使用严格大于条件 > 即可自然满足“最小层号”的要求。

4. $N \le 10^4$：

   • 分析：数据量非常小。在 NOI 环境下，$O(N)$ 甚至 $O(N \log N)$ 都能通过。这里的重点在于逻辑的严密性和对负数情况的处理。

教练点评： 本题是二叉树层序遍历的典型应用。与“每层最大值”不同，本题需要累加。在 NOI 竞赛中，处理负数极值和理解层级索引是此类题目的核心考点。记住：先算完一整层，再去更新全局最值。