为了方便你快速构建 OJ（Online Judge）测试数据，我编写了一个高效的数据生成器。它能够自动生成 10 组涵盖各种形态和权值分布的二叉树，并同步生成标准答案（.out 文件）。

设计思路

1. 判定逻辑：生成器内置了基于 BFS 的标准校验程序，使用 long long 处理层和，并严格遵循“和相等时取最小层号”的逻辑。
2. 树构造法：
   • 链状树：构造极深的树，测试 DFS 是否会爆栈（虽然本题建议 BFS）。
   • 完全/满二叉树：测试最大宽度下的层和计算。
   • 随机树：使用已入树节点作为父节点的策略，确保生成的结构一定是连通的二叉树。
3. 权值策略：
   • 全负数：测试 maxSum 是否错误地初始化为 0。
   • 平局测试：人为制造多层和相等的情况，测试层号逻辑。
   • 极端值：使用权值上下界（$\pm 10^5$）。

C++ 数据生成器源码

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <random>
#include <climits>

using namespace std;

struct Node {
    int v, l, r;
};

// ---------------- 核心算法：用于生成标准答案 (.out) ----------------
void solve(int n, const vector<Node>& tree, const string& filename) {
    ofstream fout(filename);
    if (n <= 0) return;

    queue<int> q;
    q.push(1);

    long long maxSum = -4e18; // 极小值
    int ansLevel = 1;
    int curLevel = 1;

    while (!q.empty()) {
        int sz = q.size();
        long long levelSum = 0;

        for (int i = 0; i < sz; i++) {
            int u = q.front();
            q.pop();
            levelSum += tree[u].v;
            if (tree[u].l) q.push(tree[u].l);
            if (tree[u].r) q.push(tree[u].r);
        }

        // 关键逻辑：和相等时不更新，保留最小层号
        if (levelSum > maxSum) {
            maxSum = levelSum;
            ansLevel = curLevel;
        }
        curLevel++;
    }
    fout << ansLevel << endl;
    fout.close();
}

// ---------------- 随机数工具 ----------------
mt19937 rng(42); 
int randInt(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// ---------------- 核心生成逻辑 ----------------
void generate_test_case(int t) {
    string in_name = to_string(t) + ".in";
    string out_name = to_string(t) + ".out";
    ofstream fin(in_name);

    int n = 10000; // 默认最大规模
    vector<Node> tree;
    
    // 场景分配
    if (t == 1) n = 1;                   // 边界：单节点
    else if (t == 2) n = 100;            // 小规模随机
    else if (t == 3) n = 1000;           // 全负数测试
    else if (t == 4) n = 10000;          // 满二叉树结构
    else if (t == 5) n = 10000;          // 左斜链 (极深)
    else if (t == 6) n = 10000;          // 右斜链 (极深)
    else if (t == 7) n = 10000;          // 平局测试 (多层和均为0)
    else if (t == 8) n = 10000;          // 稀疏随机树
    else if (t == 9) n = 10000;          // 权值极大值测试
    else n = 10000;                      // 综合压力测试

    tree.resize(n + 1, {0, 0, 0});
    fin << n << endl;

    // 1. 构造结构 (非递归)
    if (t == 5) { // 左斜
        for (int i = 1; i < n; i++) tree[i].l = i + 1;
    } else if (t == 6) { // 右斜
        for (int i = 1; i < n; i++) tree[i].r = i + 1;
    } else if (t == 4) { // 满二叉
        for (int i = 1; i <= n; i++) {
            if (i * 2 <= n) tree[i].l = i * 2;
            if (i * 2 + 1 <= n) tree[i].r = i * 2 + 1;
        }
    } else { // 随机树生成
        vector<int> has_space;
        has_space.push_back(1);
        for (int i = 2; i <= n; i++) {
            int p_idx = randInt(0, has_space.size() - 1);
            int p = has_space[p_idx];
            if (tree[p].l == 0) tree[p].l = i;
            else if (tree[p].r == 0) tree[p].r = i;
            
            if (tree[p].l && tree[p].r) {
                has_space.erase(has_space.begin() + p_idx);
            }
            has_space.push_back(i);
        }
    }

    // 2. 构造权值
    for (int i = 1; i <= n; i++) {
        if (t == 3) tree[i].v = randInt(-100000, -1); // 全负
        else if (t == 7) { // 平局测试：除了根以外，每层和通过正负抵消设为0
            if (i == 1) tree[i].v = -100;
            else tree[i].v = (i % 2 == 0) ? 50 : -50;
        }
        else if (t == 9) tree[i].v = 100000; // 全最大
        else tree[i].v = randInt(-100000, 100000);
    }

    // 3. 输出输入文件
    for (int i = 1; i <= n; i++) {
        fin << tree[i].v << " " << tree[i].l << " " << tree[i].r << endl;
    }
    fin.close();

    // 4. 生成答案
    solve(n, tree, out_name);
    cout << "Test Case " << t << " generated." << endl;
}

int main() {
    for (int i = 1; i <= 10; i++) {
        generate_test_case(i);
    }
    return 0;
}

测试点说明

如何部署

1. 编译：g++ gen.cpp -o gen -std=c++14 -O2。
2. 运行：./gen。
3. 结果：程序会在当前目录生成 1.in 至 10.out。
4. 文件大小：由于 $N=10^4$，每组数据约为 $150KB \sim 200KB$，10 组总计约 $2MB$，完全符合你的空间要求。

教练提示

• 非递归生成：生成逻辑中通过维护一个 has_space 列表随机抽取父节点，保证了树的连通性且不需要递归，有效防止生成器自身爆栈。
• 平局逻辑：在 Case 7 中，我故意让除第一层以外的各层之和通过正负抵消趋向于 0，而第一层和为 -100。此时最大和为 0，且出现在多个层级。标准程序应该输出层号 2。这是检验学生逻辑是否细腻的“杀手锏”。

在处理“层级累加”类问题时，核心在于如何清晰地界定每一层的边界。以下提供三个版本的代码，从 DFS 到 BFS，再到针对竞赛常数优化的版本。

版本一：深度优先搜索 (DFS)

思路： 利用递归遍历整棵树，同时传入当前深度 dep。使用一个全局数组或 vector 记录每一层的累加和。由于 DFS 不是天然按层访问，我们需要先用一个容器记录各层结果，最后再扫描一遍容器找最大值。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 10005;

struct Node {
    int v, l, r;
} tree[MAXN];

// levelSums[i] 存储第 i 层的权值之和
// 关键点：层数从 1 开始，累加和可能超过 int，建议用 long long
vector<long long> levelSums;

void dfs(int u, int dep) {
    if (u == 0) return;

    // 如果当前深度超过了已记录的层数，动态扩容
    if (dep > levelSums.size()) {
        levelSums.push_back(tree[u].v);
    } else {
        levelSums[dep - 1] += tree[u].v;
    }

    dfs(tree[u].l, dep + 1);
    dfs(tree[u].r, dep + 1);
}

int main() {
    int n;
    ios::sync_with_stdio(false); // 竞赛常用：加速 cin/cout
    cin.tie(0);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].v >> tree[i].l >> tree[i].r;
    }

    dfs(1, 1);

    long long maxSum = LLONG_MIN; // 易错点：必须初始化为极小值
    int ansLevel = 1;

    for (int i = 0; i < levelSums.size(); i++) {
        // 关键点：严格大于才更新，保证相同和时取最小层号
        if (levelSums[i] > maxSum) {
            maxSum = levelSums[i];
            ansLevel = i + 1;
        }
    }

    cout << ansLevel << endl;
    return 0;
}

版本二：广度优先搜索 (BFS) - 标准版

思路： BFS 是解决此类问题的“标准模板”。通过在循环内部获取 q.size()，可以一次性处理完当前层的所有节点，并立即计算出该层的总和进行比较。

#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 10005;
struct Node {
    int v, l, r;
} tree[MAXN];

int main() {
    int n;
    if (scanf("%d", &n) == EOF) return 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &tree[i].v, &tree[i].l, &tree[i].r);
    }

    queue<int> q;
    q.push(1);

    long long maxSum = -2e18; // 足够小的初值
    int ansLevel = 1;
    int curLevel = 1;

    while (!q.empty()) {
        int sz = q.size(); // 当前层节点数
        long long currentLevelSum = 0;

        for (int i = 0; i < sz; i++) {
            int u = q.front();
            q.pop();
            currentLevelSum += tree[u].v;

            if (tree[u].l) q.push(tree[u].l);
            if (tree[u].r) q.push(tree[u].r);
        }

        // 逻辑：更新最大和及其层号
        if (currentLevelSum > maxSum) {
            maxSum = currentLevelSum;
            ansLevel = curLevel;
        }
        curLevel++;
    }

    printf("%d\n", ansLevel);
    return 0;
}

版本三：竞赛最优复杂度版本 (静态队列 + 快读)

思路： 在 NOI 竞赛中，追求常数极致。使用手写快速读入 read() 提高 IO 效率，使用数组模拟队列 q[] 避免 std::queue 的内存分配开销。

#include <cstdio>

// 快速读入优化
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * f;
}

const int MAXN = 10005;
struct Node {
    int v, l, r;
} tree[MAXN];

int q[MAXN]; // 静态数组模拟队列

int main() {
    int n = read();
    if (n <= 0) return 0;

    for (int i = 1; i <= n; i++) {
        tree[i].v = read();
        tree[i].l = read();
        tree[i].r = read();
    }

    int head = 0, tail = 0;
    q[tail++] = 1; // 根节点入队

    long long maxSum = -2e18;
    int ansLevel = 1, curLevel = 1;

    while (head < tail) {
        int sz = tail - head; // 当前层的节点总数
        long long levelSum = 0;

        // 处理当前整层
        for (int i = 0; i < sz; i++) {
            int u = q[head++];
            levelSum += tree[u].v;
            
            if (tree[u].l) q[tail++] = tree[u].l;
            if (tree[u].r) q[tail++] = tree[u].r;
        }

        if (levelSum > maxSum) {
            maxSum = levelSum;
            ansLevel = curLevel;
        }
        curLevel++;
    }

    printf("%d\n", ansLevel);
    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 遍历：无论是 DFS 还是 BFS，每个节点及其子节点信息只会被读取 1 次。
   • 计算：每层和的比较操作次数正比于树的高度 $H$。
   • 结论：总时间复杂度为 $O(N)$。对于 $10^4$ 规模，算法运行时间远低于 1ms。

2. 空间复杂度分析：

   • 存储：静态数组 tree 占用 $O(N)$。
   • 辅助空间：
     • BFS 队列：最坏情况下（满二叉树底层）需要存储 $N/2$ 个节点，空间 $O(N)$。
     • DFS 递归：最坏情况下（链状树）递归深度为 $N$，空间 $O(N)$。
   • 结论：总空间复杂度为 $O(N)$。

时间复杂度优化建议

1. 初值选择： 不要使用 0 初始化 maxSum。在权值存在负数的题目中，这是最常见的失分点。建议使用 LLONG_MIN 或直接将第一层的和作为初始值。

2. 避免反复判断： 如果使用 BFS，每一层的节点数 sz 已经固定，通过一层循环处理完当前层，比在每个节点处理时都去判断属于哪一层要高效得多。

3. 递归与栈溢出： 虽然 $N=10^4$ 不会引起栈溢出，但在 $N \ge 10^5$ 的 NOI 题目中，如果树极度倾斜，DFS 可能会爆栈。此时建议使用 BFS 或手动模拟栈。

4. 数据类型： 虽然本题权值累加不超过 int，但在大多数 OI 题目中，累加和（Sum）建议养成使用 long long 的习惯，防止因溢出导致的 WA。

关键点总结 (易错点)

• 层号从 1 开始：注意题目描述，不要习惯性地从 0 开始。
• 平局处理：题目要求返回“最小层号”，因此在 sum == maxSum 时，不应更新层号。代码中应使用 if (levelSum > maxSum)。
• 负数权值：再次强调，maxSum 的初始值必须足够小。