为了方便你创建 OJ（Online Judge）测试数据，我编写了一个完整的数据生成器。它能够自动生成 10 组测试点，涵盖了从空树到万级节点的各类极端情况，并同步生成标准答案。

数据生成器设计思路

1. 覆盖范围：
   • 边界：$n=0$ (空树), $n=1$ (单节点), $n=10^4$ (最大规模)。
   • 形态：完全二叉树（平衡）、极度倾斜的树（链状）、随机稀疏树。
   • 数值：全负数、包含 INT_MIN 和 INT_MAX、全相等数值。
2. 效率：采用 BFS 逻辑生成树结构，时间复杂度 $O(N)$，空间复杂度 $O(N)$，不会爆栈。
3. 格式：完全符合 NOI 风格的输入输出格式。

C++ 数据生成器源码

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

using namespace std;

// 定义节点结构
struct Node {
    long long v;
    int l, r;
};

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

    queue<int> q;
    q.push(1);
    bool firstRow = true;

    while (!q.empty()) {
        int sz = q.size();
        long long levelMax = LLONG_MIN;

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

        if (!firstRow) fout << " ";
        fout << levelMax;
        firstRow = false;
    }
    fout << endl;
}

// ---------------- 随机数工具 ----------------
mt19937 rng(1337); 
long long randVal(long long minV, long long maxV) {
    uniform_int_distribution<long long> dist(minV, maxV);
    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 = 0;
    vector<Node> tree;
    long long min_v = -2147483648LL;
    long long max_v = 2147483647LL;

    // 根据测试点编号设定不同的场景
    if (t == 1) n = 0; // 空树
    else if (t == 2) n = 1; // 单节点
    else if (t == 3) n = 100; // 小规模全负数
    else if (t == 4) n = 1000; // 链状树 (最大深度)
    else if (t == 5) n = 1000; // 完全二叉树 (平衡)
    else if (t == 6) n = 5000; // 随机树 1
    else if (t == 7) n = 10000; // 规模最大值：随机树 2
    else if (t == 8) n = 10000; // 规模最大值：所有值相同
    else if (t == 9) n = 10000; // 规模最大值：包含极值
    else n = 10000; // 综合压力测试

    tree.resize(n + 1);
    fin << n << endl;

    if (n > 0) {
        // 1. 生成树结构 (l, r)
        if (t == 4) { // 链状
            for (int i = 1; i < n; ++i) tree[i].l = i + 1, tree[i].r = 0;
        } else if (t == 5) { // 完全二叉树
            for (int i = 1; i <= n; ++i) {
                tree[i].l = (2 * i <= n) ? 2 * i : 0;
                tree[i].r = (2 * i + 1 <= n) ? 2 * i + 1 : 0;
            }
        } else { // 随机结构 (使用已加入节点作为父节点)
            for (int i = 2; i <= n; ++i) {
                int parent = randVal(1, i - 1);
                if (tree[parent].l == 0) tree[parent].l = i;
                else if (tree[parent].r == 0) tree[parent].r = i;
                else i--; // 重新选父节点
            }
        }

        // 2. 生成权值 v
        for (int i = 1; i <= n; ++i) {
            if (t == 3) tree[i].v = randVal(-1000, -1);
            else if (t == 8) tree[i].v = 666;
            else if (t == 9) tree[i].v = (i % 2 == 0) ? min_v : max_v;
            else tree[i].v = randVal(min_v, max_v);
        }

        // 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 t = 1; t <= 10; ++t) {
        generate_test_case(t);
    }
    return 0;
}

数据分布说明

如何使用

1. 将上述代码保存为 gen.cpp。
2. 使用命令 g++ gen.cpp -o gen -O2 -std=c++14 编译。
3. 运行 ./gen，当前目录下会生成 1.in, 1.out ... 10.in, 10.out。
4. 生成的 .in 文件总大小约为 200KB - 300KB，完全符合你要求的 2MB 以内。

优化与注意事项

• 非递归生成：生成树结构时采用了增量编号法，确保父节点编号始终小于子节点编号，避免了复杂的拓扑排序，且生成逻辑完全是迭代的，不存在爆栈风险。
• 空间复杂度：使用了 vector<Node>，内存占用约为 $10^4 \times 16$ 字节 $\approx 160KB$，极其轻量。
• 时间复杂度：生成一千万规模的数据也只需几百毫秒，对于 $10^4$ 更是瞬间完成。
• 异常处理：在生成随机树时，通过 if (tree[parent].l == 0) 的判断确保每个节点最多只有两个孩子，避免了无效结构的产生。

在 NOI 竞赛中，虽然本题的理论最优复杂度是 $O(N)$，但代码的实现方式、内存管理和 IO 效率会直接影响程序的运行常数和稳定性。

以下是三种不同版本的题解，从基础递归到竞赛级的常数优化。

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

思路：这是最直观的写法。利用递归遍历整棵树，同时维护一个当前深度 dep。使用一个动态数组（或全局数组）记录每一层已知的最大值。

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

using namespace std;

const int MAXN = 10005;
const long long INF = 1e18; // 使用足够小的初值

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

vector<long long> res;

// u: 当前节点编号, dep: 当前深度(从0开始)
void dfs(int u, int dep) {
    if (u == 0) return;

    // 如果当前深度是第一次到达，直接存入
    if (dep == res.size()) {
        res.push_back(tree[u].val);
    } else {
        // 否则更新该层的最大值
        if (tree[u].val > res[dep]) {
            res[dep] = tree[u].val;
        }
    }

    // 递归处理子节点
    dfs(tree[u].l, dep + 1);
    dfs(tree[u].r, dep + 1);
}

int main() {
    int n;
    // 使用 fast io 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    if (n == 0) return 0; // 特判空树

    for (int i = 1; i <= n; ++i) {
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }

    dfs(1, 0);

    for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

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

思路：这是解决“每一层”问题的正统方法。利用队列 queue，每次处理前先获取队列大小 sz，这 sz 个节点即为当前层的所有节点。

#include <iostream>
#include <queue>
#include <vector>
#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 || n == 0) 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);
    
    bool firstRow = true;
    while (!q.empty()) {
        int sz = q.size();
        long long currentMax = LLONG_MIN; // 易错点：必须初始化为极小值

        for (int i = 0; i < sz; i++) {
            int u = q.front();
            q.pop();

            if (tree[u].v > currentMax) currentMax = tree[u].v;

            // 将下一层节点入队
            if (tree[u].l != 0) q.push(tree[u].l);
            if (tree[u].r != 0) q.push(tree[u].r);
        }

        if (!firstRow) printf(" ");
        printf("%lld", currentMax);
        firstRow = false;
    }
    printf("\n");

    return 0;
}

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

思路：在 NOI 考场上，若数据量达到 $10^6$，std::queue 和 cin 可能会成为瓶颈。本版本使用手写快读和数组模拟队列，将常数压到极限。

#include <cstdio>
#include <algorithm>

using namespace std;

// 手写快速读入，NOI必备
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;

    bool first = true;
    while (head < tail) {
        int sz = tail - head; // 当前层的节点数
        int levelMax = -2147483648; // 使用int最小值

        while (sz--) {
            int u = q[head++];
            if (tree[u].v > levelMax) levelMax = tree[u].v;
            
            // 静态存储判断
            if (tree[u].l) q[tail++] = tree[u].l;
            if (tree[u].r) q[tail++] = tree[u].r;
        }

        if (!first) putchar(' ');
        printf("%d", levelMax);
        first = false;
    }
    putchar('\n');

    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 无论是 DFS 还是 BFS，每个节点及其孩子信息只会被访问 1 次。
   • 对于 BFS，每个节点入队和出队各 1 次。
   • 总操作次数正比于 $N$，故时间复杂度为 $O(N)$。
   • 优化建议：当 $N$ 很大时，主要瓶颈在于 getchar() 与 putchar() 的 IO 次数。

2. 空间复杂度分析：

   • 树存储：使用了静态数组 tree[MAXN]，空间为 $O(N)$。
   • BFS 队列：最坏情况下（完全二叉树最后一层），队列中会同时存在 $N/2$ 个节点，空间为 $O(N)$。
   • DFS 递归栈：最坏情况下（树退化为链），递归深度为 $N$，空间为 $O(N)$。在 NOI 竞赛中，若遇到深度过大的树，需注意系统栈限制（可以使用 -Wl,--stack=134217728 扩大栈或改写为 BFS）。

易错点总结（教练寄语）

1. 初始值陷阱： 很多同学习惯将 maxVal 初始化为 0。但在本题中，节点权值可以是负数。如果某一层全是 -5, -10，初始值为 0 就会导致错误结果。必须初始化为 INT_MIN 或第一个节点的值。

2. 空树特判： 当 $n=0$ 时，程序不应有任何输出或应安全退出。直接访问 tree[1] 会导致越界。

3. 输出格式： NOI 题目通常对行末空格不敏感，但对每行开头的空格或多余换行敏感。建议使用 first 标记位来控制空格。

4. 数据范围： 虽然本题权值在 int 范围内，但如果要进行加法运算（比如求每层总和），则必须使用 long long 以防溢出。养成看到大数就思考是否需要 long long 的习惯。