为了满足你创建 OJ（Online Judge）测试数据的需求，我编写了这个高性能、防爆栈的数据生成器。它采用 C++14 标准，能够自动生成 1-10 号测试点（.in 文件）并利用迭代法计算出标准答案（.out 文件）。

数据生成器设计策略

1. 分级测试点：
   • 1-3 (基础/边界)：空树 ($n=0$)、单根节点 ($n=1$)、小规模树。
   • 4 (极端链状)：$n=10000$，深度为 $10000$。专门卡递归深度，如果选手的代码没开栈优化或没写迭代，会 RE。
   • 5 (极端星形)：$n=10000$，根节点连着所有子节点。测试对宽度的处理。
   • 6-10 (大规模随机)：$n$ 逐渐增大至 $10000$，采用随机亲缘关系构造，涵盖稀疏和稠密分叉。
2. 安全性：生成器内置的 get_postorder 采用迭代法（根-右-左再反转），确保即使生成 $10^6$ 级别的链状树也不会因爆栈而崩溃。
3. 性能：使用 std::mt19937 随机引擎和 $O(N)$ 构树算法。

C++ 数据生成器代码

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <random>
#include <stack>
#include <string>

using namespace std;

// 定义节点结构
struct Node {
    int val;
    vector<int> children;
};

// ---------------------------------------------------------
// 核心：非递归（迭代）后序遍历，用于生成标程答案
// 算法：根-右-左 遍历后进行全序列反转
// ---------------------------------------------------------
vector<int> solve_postorder(int n, const vector<Node>& tree) {
    if (n <= 0) return {};
    vector<int> res;
    res.reserve(n);
    stack<int> st;
    st.push(0); // 假设 0 始终是根节点

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        res.push_back(tree[u].val);

        // 为了实现弹出的顺序是“从右到左”，压栈必须“从左到右”
        for (int child_id : tree[u].children) {
            st.push(child_id);
        }
    }
    // 反转 (根-右-左) -> (左-右-根)
    reverse(res.begin(), res.end());
    return res;
}

// ---------------------------------------------------------
// 随机树生成逻辑
// ---------------------------------------------------------
void generate_test_case(int id, int n, int type) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    if (n == 0) {
        fin << 0 << endl;
        return;
    }

    vector<Node> tree(n);
    mt19937 rng(id + 2025); // 固定种子保证可复现
    uniform_int_distribution<int> val_dist(1, 1000000);

    for (int i = 0; i < n; ++i) tree[i].val = val_dist(rng);

    if (type == 4) { // 链状树 (Bamboo)
        for (int i = 0; i < n - 1; ++i) tree[i].children.push_back(i + 1);
    } 
    else if (type == 5) { // 星形树 (Star)
        for (int i = 1; i < n; ++i) tree[0].children.push_back(i);
    } 
    else if (id == 3) { // 特殊构造：匹配 LeetCode 示例 1
        // [1,null,3,2,4,null,5,6] -> 6 nodes
        // 这里模拟：1(0)的孩子是 3(1), 2(2), 4(3)；3(1)的孩子是 5(4), 6(5)
        tree.clear(); tree.resize(6);
        tree[0] = {1, {1, 2, 3}};
        tree[1] = {3, {4, 5}};
        tree[2] = {2, {}};
        tree[3] = {4, {}};
        tree[4] = {5, {}};
        tree[5] = {6, {}};
    }
    else { // 随机树 (Random)
        for (int i = 1; i < n; ++i) {
            // 保证父节点编号小于子节点，绝对不会产生环
            int p = uniform_int_distribution<int>(0, i - 1)(rng);
            tree[p].children.push_back(i);
        }
        // 打乱每个节点的子节点顺序，增加测试强度
        for (int i = 0; i < n; ++i) {
            shuffle(tree[i].children.begin(), tree[i].children.end(), rng);
        }
    }

    // 写入 .in 文件
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << tree[i].val << " " << tree[i].children.size();
        for (int child_id : tree[i].children) {
            fin << " " << child_id;
        }
        fin << "\n";
    }

    // 生成标准输出并写入 .out 文件
    vector<int> ans = solve_postorder(n, tree);
    for (int i = 0; i < ans.size(); ++i) {
        fout << ans[i] << (i == (int)ans.size() - 1 ? "" : " ");
    }
    if (n > 0) fout << endl;

    fin.close();
    fout.close();
    cout << "Test Case " << id << " [n=" << n << "] generated." << endl;
}

int main() {
    // 1-3 基础与示例
    generate_test_case(1, 0, 0);      // 空树
    generate_test_case(2, 1, 0);      // 单根
    generate_test_case(3, 6, 0);      // LeetCode 示例 1 结构

    // 4-5 极端结构 (n = 10000)
    generate_test_case(4, 10000, 4);  // 链状
    generate_test_case(5, 10000, 5);  // 星形

    // 6-10 随机树 (规模逐渐增大)
    for (int i = 6; i <= 10; ++i) {
        int size = (i == 10) ? 10000 : i * 1000;
        generate_test_case(i, size, 0);
    }

    return 0;
}

使用说明及优化重点

1. 文件大小控制：

   • 该生成器产生的 .in 文件格式为：值 孩子数 孩子ID...。
   • 对于 $n=10000$ 的数据点，每个整数平均 5 字节，加上空格和换行，单个文件约 $150KB \sim 200KB$。
   • 10 个测试点总大小约 1.5MB，完全符合你要求的 2MB 以内。

2. 避免异常 (Exception)：

   • 除零：本算法完全不涉及除法运算，避开了除零风险。
   • 内存越界：使用 vector 和 stack 动态管理，并在 n=0 时进行了特判。
   • 爆栈 (Stack Overflow)：无论是构树逻辑（i 选 0~i-1 作为父节点）还是答案生成逻辑（迭代法），都未使用递归。

3. 时间复杂度优化：

   • 构树：$O(N)$。每个节点只被分配一次父节点。
   • 答案生成：$O(N)$。使用了 vector::reserve 预分配空间，避免了多次内存拷贝。
   • 洗牌 (Shuffle)：$O(N)$。通过 std::shuffle 保证子节点顺序随机。

4. OJ 设置建议：

   • 由于 4.in 是深度为 10000 的链状树，请确保 OJ 的系统栈限制（Stack Limit）不要设得太死（建议 64MB 以上），或者在题目说明中提示学生注意递归深度。

这个生成器产生的 3.in 和 3.out 将完美匹配 LeetCode 示例 1 的逻辑，帮助你快速验证程序的正确性。

作为你的教练，我将为你展示从基础递归实现到工业级迭代优化的演进过程。在 NOI 竞赛中，递归是最直观的，但迭代法在处理超大规模数据（防止栈溢出）时具有更高的稳定性。

版本一：基础递归 DFS（最直观的 NOI 满分思路）

思路分析： 利用递归的特性。在进入子节点递归逻辑后，才记录当前节点的值。

• 时间复杂度：$O(N)$，每个节点访问一次。
• 空间复杂度：$O(H)$，系统栈深度取决于树高。最坏情况下（链状树）为 $O(N)$。

#include <iostream>
#include <vector>

using namespace std;

// NOI 习惯：使用静态数组存储树结构，MAXN 根据题目范围设定
const int MAXN = 10005;

struct Node {
    int val;
    vector<int> children; // 存储子节点的编号
} tree[MAXN];

vector<int> ans;

void dfs(int u) {
    // 【关键点】按照题目要求，从左到右遍历子节点
    for (int i = 0; i < tree[u].children.size(); ++i) {
        int v = tree[u].children[i];
        dfs(v);
    }
    // 【易错点】后序遍历：处理完所有子节点后，再将自己加入答案
    ans.push_back(tree[u].val);
}

int main() {
    // 基础优化：加快输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n) || n == 0) return 0;

    // 读入：编号 0..n-1，每个节点包含值、孩子数、孩子编号
    for (int i = 0; i < n; ++i) {
        int v, k;
        cin >> v >> k;
        tree[i].val = v;
        for (int j = 0; j < k; ++j) {
            int child_id;
            cin >> child_id;
            tree[i].children.push_back(child_id);
        }
    }

    dfs(0); // 从根节点（编号0）开始

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

    return 0;
}

版本二：迭代法（使用“反转法”技巧，避开系统栈限制）

思路分析： 在处理 N 叉树时，直接写后序迭代比较复杂。

• 观察：后序遍历是 左 -> 右 -> 根。

• 它的逆序是 根 -> 右 -> 左。

• 我们可以先模拟 根 -> 右 -> 左 的顺序（类似前序，但子节点从左往右压栈，弹出就是从右往左），最后统一 reverse。

• 时间复杂度：$O(N)$。

• 空间复杂度：$O(N)$，手动维护栈。

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

using namespace std;

const int MAXN = 10005;
int val[MAXN];
vector<int> adj[MAXN];

int main() {
    int n;
    if (!(cin >> n) || n == 0) return 0;

    for (int i = 0; i < n; ++i) {
        int k;
        cin >> val[i] >> k;
        for (int j = 0; j < k; ++j) {
            int child;
            cin >> child;
            adj[i].push_back(child);
        }
    }

    vector<int> res;
    stack<int> st;
    st.push(0);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        res.push_back(val[u]); // 此时顺序是：根 -> 右 -> 左

        // 【关键点】为了实现弹出顺序是“从右到左”，压栈顺序应为“从左到右”
        for (int i = 0; i < adj[u].size(); ++i) {
            st.push(adj[u][i]);
        }
    }

    // 【核心步】将 (根-右-左) 翻转得到 (左-右-根)
    reverse(res.begin(), res.end());

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

    return 0;
}

版本三：最优复杂度优化版（NOI 考场极限性能）

思路分析： 当 $N$ 达到 $10^6$ 量级时，vector 的频繁内存分配和 cin 的性能会成为瓶颈。

• 优化点 1：使用 scanf/printf。
• 优化点 2：对 vector 使用 reserve() 减少重分配。
• 优化点 3：结果数组预分配空间，直接下标填值。

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
int node_val[MAXN];
vector<int> adj[MAXN];
int result[MAXN];

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;

    for (int i = 0; i < n; ++i) {
        int k;
        scanf("%d %d", &node_val[i], &k);
        adj[i].reserve(k); // 提前预留内存，减少 push_back 时的重分配开销
        for (int j = 0; j < k; ++j) {
            int child;
            scanf("%d", &child);
            adj[i].push_back(child);
        }
    }

    stack<int> st;
    st.push(0);
    int top = 0;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        result[top++] = node_val[u];

        // 顺序处理子节点
        for (int v : adj[u]) {
            st.push(v);
        }
    }

    // 手动反转数组，比 std::reverse 略快且节省内存
    for (int i = 0; i < top / 2; ++i) {
        swap(result[i], result[top - 1 - i]);
    }

    for (int i = 0; i < top; ++i) {
        printf("%d%c", result[i], (i == top - 1 ? '\n' : ' '));
    }

    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 遍历：树共有 $N$ 个节点，$N-1$ 条边。无论递归还是迭代，每条边被扫描一次，每个节点入栈/出栈一次。复杂度 $O(N)$。
   • 反转：对长度为 $N$ 的数组进行反转，复杂度 $O(N)$。
   • 结论：总时间复杂度 $O(N)$，已是理论最优。

2. 空间复杂度分析：

   • 存储：邻接表存储所有边，空间 $O(N)$。
   • 辅助空间：栈空间 $O(H)$（树高），结果数组 $O(N)$。
   • 结论：总空间复杂度 $O(N)$。

3. 时间复杂度优化建议：

   • 内存池（Static Pool）：在极高要求的题目中，如果子节点非常多，可以用静态数组模拟邻接表（链式前向星），彻底消除 std::vector 的开销。
   • 快读（Fast I/O）：如果 $N > 10^6$，使用 getchar() 实现的快读函数比 scanf 快 3-5 倍。

总结：读题关键词在哪里？

1. “后序”：
   • 如果是递归，代码位置在“递归调用后”。
   • 如果是迭代，记得“反转法”：Reverse(根 -> 右 -> 左)。
2. “从左到右”：
   • 这决定了你 push_back 的顺序。如果顺序错了，在迭代法的栈里弹出的顺序也会错。
3. “N 叉树”：
   • 意味着不能用 Node *left, *right，必须用 vector 或数组模拟。
4. 数据范围 $10^4$：
   • 这个范围提示我们：$O(N)$ 是稳过的，且递归深度不会爆栈（通常 Linux 默认栈大小为 8MB，支持约 $10^5$ 层递归）。如果是 $10^6$，则必须考虑迭代。