#include <bits/stdc++.h>

using namespace std;

struct node{
    int val;
    int l,r;
};//注意这里要有分号

node tree[2005];

int main() {
    int n;
    cin>>n;
    if(n==0){
        return 0;
    }
    for(int i=0;i<n;i++){
        cin>>tree[i].l>>tree[i].r;
    }
    for(int i=0;i<n;i++){
        cin>>tree[i].val;
    }
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int size=q.size();//记录当前层有几个节点
        while(size--){//处理当前层，注意过程中q可能会增加节点所以不能用q.size()
            int u=q.front();//获取当前队首的元素值
            q.pop();//弹出(移除)队首
            cout<<tree[u].val;
            cout<<" ";//当前层还没结束，输出空格
            //当前节点的左右儿子节点需要加入队列，排队待办
            //因为我们已经记录了当前层的元素个数size所以队列变长不会影响当前层的处理
            if(tree[u].l!=-1){
                q.push(tree[u].l);
            }
            if(tree[u].r!=-1){
                q.push(tree[u].r);
            }
        }
        cout<<endl;//每层结束后换行        
    }
    return 0;
}

非常抱歉，这是我的疏忽。错误的原因在于 C++ <random> 库的设计逻辑：

错误点： dist(rng()) 原因： std::uniform_int_distribution 的 operator() 接收的是随机数生成器对象本身（引用传递），以便在内部多次调用并更新生成器的状态。而 rng() 会直接运行生成器并返回一个具体的数值（右值），导致编译器无法将这个数值绑定到左值引用上。

修复方法： 将 dist(rng()) 改为 dist(rng)。

以下是修复后的完整代码，我同时优化了随机种子的生成方式，确保在短时间内生成多个测试点时随机性更强。

修复后的数据生成器 (gen.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <random>
#include <string>
#include <ctime>
#include <chrono>

using namespace std;

// --- 核心解题逻辑 (用于生成 .out 文件) ---
// 采用标准 BFS 分层逻辑，确保生成的 .out 文件绝对正确
void solve(string in_name, string out_name) {
    ifstream cin(in_name);
    ofstream cout(out_name);

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

    vector<int> ls(n), rs(n), vs(n);
    for (int i = 0; i < n; i++) cin >> ls[i] >> rs[i];
    for (int i = 0; i < n; i++) cin >> vs[i];

    queue<int> q;
    q.push(0); // 根节点始终为 0
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int u = q.front();
            q.pop();
            cout << vs[u] << (i == sz - 1 ? "" : " ");
            if (ls[u] != -1) q.push(ls[u]);
            if (rs[u] != -1) q.push(rs[u]);
        }
        cout << "\n";
    }
}

// --- 数据构造逻辑 ---
void make_data(int test_id, int n, string type) {
    string in_name = to_string(test_id) + ".in";
    string out_name = to_string(test_id) + ".out";
    ofstream cout(in_name);

    // 处理空树边界
    if (n == 0) {
        cout << 0 << endl;
        cout.close();
        ofstream out_file(out_name);
        out_file.close();
        return;
    }

    cout << n << "\n";
    
    vector<int> ls(n, -1), rs(n, -1);
    // 使用高精度时间戳作为种子
    auto seed = chrono::high_resolution_clock::now().time_since_epoch().count() + test_id;
    mt19937 rng(seed);

    // 1. 生成树结构
    if (type == "line_left") { 
        for (int i = 0; i < n - 1; i++) ls[i] = i + 1;
    } 
    else if (type == "line_right") { 
        for (int i = 0; i < n - 1; i++) rs[i] = i + 1;
    }
    else if (type == "balanced") { 
        for (int i = 0; i < n; i++) {
            if (2 * i + 1 < n) ls[i] = 2 * i + 1;
            if (2 * i + 2 < n) rs[i] = 2 * i + 2;
        }
    }
    else { // 随机树生成逻辑
        for (int i = 1; i < n; i++) {
            // 将节点 i 随机挂载到 0 到 i-1 之间的某个未满节点上
            while (true) {
                int p = uniform_int_distribution<int>(0, i - 1)(rng);
                if (ls[p] == -1) { ls[p] = i; break; }
                else if (rs[p] == -1) { rs[p] = i; break; }
            }
        }
    }

    // 2. 写入节点关系
    for (int i = 0; i < n; i++) {
        cout << ls[i] << " " << rs[i] << "\n";
    }

    // 3. 生成随机值并写入
    uniform_int_distribution<int> dist(-1000, 1000);
    for (int i = 0; i < n; i++) {
        // 修复点：传入 rng 对象引用而非 rng() 返回值
        cout << dist(rng) << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    cout.close();
    
    // 4. 调用标程生成对应的 .out 文件
    solve(in_name, out_name);
}

int main() {
    printf("Generating 10 test cases...\n");

    make_data(1, 0, "empty");       // 边界：空树
    make_data(2, 1, "single");      // 边界：单节点
    make_data(3, 10, "line_left");  // 特殊：左斜树
    make_data(4, 10, "line_right"); // 特殊：右斜树
    make_data(5, 15, "balanced");   // 典型：完全二叉树
    make_data(6, 100, "random");    // 中等：随机
    make_data(7, 500, "random");    // 中等：随机
    make_data(8, 2000, "line_left");// 极限：最深（2000层）
    make_data(9, 2000, "balanced"); // 极限：最宽（完全二叉树最后层约1024个点）
    make_data(10, 2000, "random");  // 综合：大数据随机

    printf("Success! Files 1.in/out to 10.in/out are ready.\n");
    return 0;
}

编译说明

请使用以下命令编译，确保开启了 C++11 或以上标准（NOIP 现已全面支持 C++14）：

g++ -O2 -Wall gen.cpp -o gen.exe -std=c++14

为什么之前报错？（教练笔记）

这是 std::uniform_int_distribution 的一个经典坑：

• rng 是一个引擎类（Engine），负责产生原始的随机位。
• dist 是一个分布类（Distribution），负责把这些位映射到你需要的区间（比如 -1000 到 1000）。
• dist(rng)：调用时，dist 内部会多次调用 rng 的成员函数来获取随机位。因此它需要 rng 的引用来改变 rng 内部的状态（计数器等）。
• 如果你写 dist(rng())，编译器会先执行 rng() 得到一个随机整数（比如 42），然后尝试把这个 42 传给 dist。由于 dist 要求的是一个“能产生随机数的机器”而不是一个“死数字”，所以报错。

在 NOI 系列竞赛（如 NOIP、CSP-S）中，处理树形结构题目时，代码的稳定性和运行效率至关重要。

由于这道题本身的时间复杂度下限就是 $O(N)$（每个节点必须访问一次），我们优化的重点在于减少内存分配开销、防止递归栈溢出以及提升代码在底层评测机上的执行速度。

以下是三个版本的代码，从简单的递归逻辑到竞赛级别的数组优化版本。

版本一：递归深度优先搜索 (DFS) 模拟层序

思路：虽然是层序遍历，但我们可以通过 DFS 记录当前节点的“深度”。通过深度作为索引，将节点值填入对应的 vector 中。 优点：代码极其简洁，适合在比赛时间紧迫时快速实现。

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

using namespace std;

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];
vector<vector<int>> res;

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

    // 如果当前深度超过了 res 的现有大小，说明进入了新的一层
    if (d >= res.size()) {
        res.push_back(vector<int>());
    }

    res[d].push_back(val[u]); // 将当前节点值加入对应深度的 vector
    dfs(l_son[u], d + 1);      // 递归左子树，深度+1
    dfs(r_son[u], d + 1);      // 递归右子树，深度+1
}

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

    // NOI 风格输入：节点关系存储
    for (int i = 0; i < n; i++) {
        cin >> l_son[i] >> r_son[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }

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

    // 输出结果
    for (const auto& level : res) {
        for (int i = 0; i < level.size(); i++) {
            cout << level[i] << (i == level.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

复杂度分析：

• 时间：$O(N)$，每个节点访问一次。
• 空间：$O(H)$，$H$ 为树的高度。最坏情况下（链状树）空间复杂度为 $O(N)$，可能会触发栈溢出（但在 $N=2000$ 时安全）。

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

思路：使用 std::queue。为了分层，在处理每一层之前先记录当前队列的大小 sz。 优点：逻辑最符合“层序遍历”的本质，由于没有递归，完全不用担心栈溢出。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    for (int i = 0; i < n; i++) cin >> l_son[i] >> r_son[i];
    for (int i = 0; i < n; i++) cin >> val[i];

    queue<int> q;
    q.push(0); // 假设 0 是根节点

    while (!q.empty()) {
        int sz = q.size(); // 关键点：当前队列里的节点全属于同一层
        vector<int> current_level;

        while (sz--) {
            int u = q.front();
            q.pop();
            current_level.push_back(val[u]);

            // 易错点：入队前必须判断子节点是否存在（本题用 -1 表示不存在）
            if (l_son[u] != -1) q.push(l_son[u]);
            if (r_son[u] != -1) q.push(r_son[u]);
        }

        // 输出当前层
        for (int i = 0; i < current_level.size(); i++) {
            cout << current_level[i] << (i == current_level.size() - 1 ? "" : " ");
        }
        cout << "\n"; // 使用 \n 替代 endl，在大数据量下更快
    }

    return 0;
}

复杂度分析：

• 时间：$O(N)$。
• 空间：$O(W)$，$W$ 为树的最大宽度。

版本三：竞赛级优化（数组模拟队列与预分配空间）

思路：在 NOI 提高组中，如果 $N$ 达到 $10^6$，std::vector 的频繁扩容和 std::queue 的动态分配会变慢。我们使用静态数组模拟队列，并直接根据每一层的节点数进行处理。

#include <cstdio> // 使用 fast I/O 或 scanf

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];
int q[MAXN]; // 静态数组模拟队列，极其高效

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

    for (int i = 0; i < n; i++) scanf("%d %d", &l_son[i], &r_son[i]);
    for (int i = 0; i < n; i++) scanf("%d", &val[i]);

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

    while (head < tail) {
        int sz = tail - head; // 当前层的节点数量
        
        // 技巧：在这一步，q[head] 到 q[tail-1] 存储的就是当前层所有节点编号
        for (int i = 0; i < sz; i++) {
            int u = q[head + i];
            printf("%d%c", val[u], (i == sz - 1 ? '\n' : ' '));
        }

        // 将下一层节点加入队尾，注意不要修改当前的 head
        int next_level_count = 0;
        for (int i = 0; i < sz; i++) {
            int u = q[head++]; // 真正弹出当前层
            if (l_son[u] != -1) q[tail++] = l_son[u];
            if (r_son[u] != -1) q[tail++] = r_son[u];
        }
    }

    return 0;
}

总结与优化建议

1. 时间复杂度分析思考过程

• 访问控制：无论 BFS 还是 DFS，树的结构保证了没有环，因此不需要 vis[] 数组。每个节点进出队列各一次，时间复杂度严格 $O(N)$。
• 优化方向：在 $N$ 很大时，std::endl 会刷新缓冲区导致速度变慢，务必使用 \n。std::vector 的 push_back 具有均摊 $O(1)$ 的复杂度，但在竞赛中，如果能预估大小，使用 vector::reserve() 可以减少 30% 以上的耗时。

2. 空间复杂度优化建议

• 内存池：在处理大规模树结构时，尽量避开 new 关键字申请内存，改用数组下标模拟指针，这能有效避免内存碎片的产生。
• 复用空间：如果只需要输出而不需要保存所有结果，可以像版本三那样，在输出当前层后立即释放或覆盖，将空间复杂度压制在 $O(W)$（树的最大宽度）。

3. 易错点总结

• 空树处理：$n=0$ 时如果不特判，q.front() 或 val[0] 可能会导致越界。
• 队列长度更新：在 BFS 循环内部，q.size() 是动态变化的。必须在处理每层前先用一个变量 sz 固定住当前层的节点数，否则会把刚入队的下一层节点也一起处理了。
• 节点编号：注意题目中节点编号是从 0 开始还是从 1 开始。如果是从 1 开始，数组大小要开 MAXN + 1。

4. 关键词识别

• “按层” $\rightarrow$ 锁定 BFS。
• “从左到右” $\rightarrow$ 确定子节点入队顺序：q.push(left); q.push(right);。
• “每一层”作为一个整体输出 $\rightarrow$ 确定需要使用 sz = q.size() 逻辑进行分层控制。