为了方便你快速构建 OJ（Online Judge）测试数据，我编写了一个高度鲁棒的数据生成器。它能够自动生成符合 NOI 竞赛要求的 10 组测试点，涵盖了从单节点到万级节点、从平衡树到极端链状树的所有情况，并同步生成标准答案（.out）。

数据生成器设计亮点：

1. 结构多样性：支持生成完全二叉树（平衡）、左/右斜向链（深层）、随机稀疏树。
2. 溢出与精度测试：专门设计了权值为 INT_MAX 的累加测试（考查 long long）和产生无限循环小数的除法测试（考查 double 精度）。
3. 安全性：所有生成算法均为 非递归迭代实现，绝不爆栈。
4. 性能：生成 $10^4$ 规模的数据及答案仅需几十毫秒。

C++ 数据生成器源码

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

using namespace std;

// 节点结构体
struct Node {
    long long v; // 权值
    int 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); // 根节点固定为1
    bool firstRow = true;

    fout << fixed << setprecision(5); // 强制五位小数

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

        for (int i = 0; i < sz; ++i) {
            int u = q.front();
            q.pop();
            sum += 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 << " ";
        // 关键点：强制转换 double 避免精度丢失和除零
        fout << (double)sum / count;
        firstRow = false;
    }
    fout << endl;
}

// ---------------- 随机数工具 ----------------
mt19937 rng(42); 
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;
    long long min_v = -2147483648LL;
    long long max_v = 2147483647LL;

    // 测试点场景分配
    if (t == 1) n = 1;                   // 边界：单节点
    else if (t == 2) n = 10;             // 小规模随机
    else if (t == 3) n = 1000;           // 完全二叉树
    else if (t == 4) n = 2000;           // 左斜链 (极深)
    else if (t == 5) n = 2000;           // 右斜链 (极深)
    else if (t == 6) n = 10000;          // 随机大规模
    else if (t == 7) n = 10000;          // 溢出测试：全为最大值
    else if (t == 8) n = 10000;          // 溢出测试：全为最小值
    else if (t == 9) n = 10000;          // 精度测试：交替正负
    else n = 10000;                      // 综合压力测试

    vector<Node> tree(n + 1, {0, 0, 0});
    fin << n << endl;

    if (n > 0) {
        // 1. 构造拓扑结构 (确保是二叉树且无环)
        if (t == 3) { // 完全二叉树
            for (int i = 1; i <= n; ++i) {
                if (2 * i <= n) tree[i].l = 2 * i;
                if (2 * i + 1 <= n) tree[i].r = 2 * i + 1;
            }
        } else if (t == 4) { // 左斜
            for (int i = 1; i < n; ++i) tree[i].l = i + 1;
        } else if (t == 5) { // 右斜
            for (int i = 1; i < n; ++i) tree[i].r = i + 1;
        } else { // 随机树生成
            vector<int> free_slots;
            free_slots.push_back(1);
            for (int i = 2; i <= n; ++i) {
                int p_idx = randVal(0, free_slots.size() - 1);
                int p = free_slots[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 != 0 && tree[p].r != 0) {
                    free_slots.erase(free_slots.begin() + p_idx);
                }
                free_slots.push_back(i);
            }
        }

        // 2. 构造权值
        for (int i = 1; i <= n; ++i) {
            if (t == 7) tree[i].v = max_v;
            else if (t == 8) tree[i].v = min_v;
            else if (t == 9) tree[i].v = (i % 2 == 0) ? 1 : 2; // 产生 1.5 或 1.33...
            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();
    solve(n, tree, out_name); // 生成答案
    cout << "Test Case " << t << " [n=" << n << "] generated." << endl;
}

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

测试点详细分布表

使用说明：

1. 编译环境：使用支持 C++11 或更高标准的编译器（如 g++ gen.cpp -o gen -std=c++14）。
2. 运行：执行 ./gen 后，本地目录会生成 1.in 到 10.out 共 20 个文件。
3. 数据大小：
   • 每个节点在输入文件中占用约 20 字节。
   • $N=10^4$ 的文件约 $200KB$。
   • 10 组数据总大小约 $1.5MB \sim 2MB$，完全符合理想范围。
4. OJ 适配：输出严格遵循空格分隔，行末换行，实数保留 5 位小数，可直接上传至主流 OJ 系统（如 HUSTOJ, Hydro, QingdaoU OJ 等）。

在 NOI 竞赛中，处理树结构时，由于 $N=10^4$ 且权值为 $32$ 位整数，计算总和时的溢出问题和层级划分的准确性是考核重点。

以下提供三个版本的代码：从直观的 DFS 到标准的 BFS，再到针对竞赛常数优化的版本。

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

思路：利用递归遍历树。我们需要两个全局数组（或 vector）分别记录每一层的“权值之和”及“节点数量”。由于 DFS 不是天然按层处理，我们需要传递一个 depth 参数。

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

const int MAXN = 10005;

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

// sums 存储每一层的权值总和，counts 存储每一层的节点个数
vector<long long> sums; // 关键点：sum必须用long long防止累加溢出
vector<int> counts;

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

    // 如果是第一次到达这一深度，初始化容器
    if (depth == sums.size()) {
        sums.push_back(tree[u].v);
        counts.push_back(1);
    } else {
        sums[depth] += tree[u].v;
        counts[depth]++;
    }

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

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

    dfs(1, 0);

    // 设置输出精度为小数点后5位
    cout << fixed << setprecision(5);
    for (int i = 0; i < sums.size(); ++i) {
        cout << (double)sums[i] / counts[i] << (i == sums.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

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

思路：使用 std::queue 进行层序遍历。通过在每一层开始前记录 q.size()，可以精确地一次性处理掉当前层的所有节点。这种方法在求平均值时最节省空间，因为不需要额外存储所有层的和。

#include <cstdio>
#include <queue>

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);

    bool first = true;
    while (!q.empty()) {
        int sz = q.size(); // 当前层的节点总数
        long long levelSum = 0; // 易错点：必须用long long累加

        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 (!first) printf(" ");
        // 关键点：计算时强制转换为 double 保证精度
        printf("%.5f", (double)levelSum / sz);
        first = false;
    }
    printf("\n");

    return 0;
}

版本三：竞赛级优化版 (静态队列 + 快读)

思路：在 NOI 考场上，若 $N$ 很大，std::queue 的动态内存分配和 scanf 可能变慢。使用手写 read() 和静态数组模拟队列可以达到最优性能。

#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;

    bool first = true;
    while (head < tail) {
        int sz = tail - head; // 计算当前层的宽度
        long long sum = 0;
        int count = sz;

        for (int i = 0; i < sz; i++) {
            int u = q[head++];
            sum += 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("%.5f", (double)sum / count);
        first = false;
    }
    putchar('\n');

    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 遍历过程：无论是 DFS 还是 BFS，每个节点及其孩子信息只会被访问 1 次。
   • 计算过程：每个节点参与 1 次 sum 的加法运算。
   • 结论：总操作次数与 $N$ 成线性关系，时间复杂度为 $O(N)$。对于 $N=10^4$，由于常数极小，耗时基本可以忽略不计。

2. 空间复杂度分析：

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

时间复杂度优化建议

1. 避免浮点数作为中间变量： 在求和过程中始终使用 long long 整数累加。如果在累加过程中每一步都除以 $N$（例如：avg += (double)val/n），由于浮点数精度限制，最后的结果可能会有微小误差，导致 OJ 评测不通过。

2. 静态分配空间： 在 NOI 竞赛中，如果 $N$ 的范围确定，尽量开全局静态数组而不是在循环内声明 vector 或 queue，这样可以避免系统频繁分配内存带来的耗时。

3. IO 提速： 当输出大量浮点数时，printf 往往比 cout 配合 setprecision 更快且代码更简洁。对于输入，若 $N \ge 10^5$，请务必使用快读。

关键点总结 (易错点)

• 数据溢出：权值是 int，但 $10^4$ 个 int 相加会超出 int 范围（约 $2 \times 10^9$），必须使用 long long。
• 除零错误：虽然树中有节点，但逻辑上要确保 count 不为 0。
• 输出格式：注意题目要求的保留位数（通常是 5 位），且注意每两个数字之间的空格处理。