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

数据生成器设计思路

1. 判定逻辑：生成器内置了一个基于 BFS 的标准校验程序。通过层序遍历，最后一层累加的结果即为标准答案。
2. 树构造策略：
   • 极深链状树：构造深度为 $10^4$ 的左斜链、右斜链和之字形链。这类数据专门用来“卡”掉那些没有人工增加系统栈空间且使用递归 DFS 的程序。
   • 宽大平衡树：构造完全二叉树，测试 BFS 队列的承载能力和宽度处理。
   • 随机连通树：通过“父节点池”随机挑选尚有空余位置的节点作为父节点，确保生成的是一棵合法的连通二叉树。
3. 安全性：生成算法采用 非递归（迭代） 逻辑，确保生成 $N=10^4$ 的长链时不会导致生成器自身爆栈。

C++ 数据生成器源码

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

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
    long long last_sum = 0;

    while (!q.empty()) {
        int sz = q.size();
        last_sum = 0; // 每进入新的一层，重置累加器
        for (int i = 0; i < sz; i++) {
            int u = q.front();
            q.pop();
            last_sum += tree[u].v;
            if (tree[u].l != 0) q.push(tree[u].l);
            if (tree[u].r != 0) q.push(tree[u].r);
        }
    }
    fout << last_sum << endl;
    fout.close();
}

// ---------------- 随机数工具 ----------------
mt19937 rng(1337); 
long long randVal(long long l, long long r) {
    uniform_int_distribution<long long> 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; // 默认最大规模
    if (t == 1) n = 1;
    if (t == 2) n = 10;

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

    // 1. 构造结构（非递归）
    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 if (t == 6) { // 之字形链
        for (int i = 1; i < n; i++) {
            if (i % 2 == 1) tree[i].l = i + 1;
            else tree[i].r = i + 1;
        }
    } else if (t == 3) { // 完全二叉树
        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> parent_pool; // 存放还有空位的节点
        parent_pool.push_back(1);
        for (int i = 2; i <= n; i++) {
            int p_idx = randVal(0, parent_pool.size() - 1);
            int p = parent_pool[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) {
                parent_pool.erase(parent_pool.begin() + p_idx);
            }
            parent_pool.push_back(i); // 新节点作为潜在父节点入池
        }
    }

    // 2. 填充权值
    for (int i = 1; i <= n; i++) {
        if (t == 9) tree[i].v = 100000000; // 测试大数累加
        else tree[i].v = randVal(1, 100);
    }

    // 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 << " [n=" << n << "] 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 编译后运行 ./gen 即可。
2. 文件大小：由于 $N$ 最大为 $10^4$，单组输入文件大小约为 $150 \sim 200 KB$。10 组数据的总大小在 $2 MB$ 左右，非常适合在校园网或资源受限的 OJ 上传输。
3. OJ 设置提示：
   • 本题建议设置时间限制为 1.0s，内存限制为 128MB。
   • 对于测试点 4, 5, 6，如果选手的代码使用了 DFS 且没有在编译器选项中增加栈空间，可能会发生 Runtime Error。这是 NOI 选手的必修课（学习如何处理深层递归或改用 BFS）。
   • 溢出风险：最深层节点最多可达 $10^4$ 个，若权值均为 $10^8$，总和为 $10^{12}$，已超过 int（$2 \times 10^9$），选手必须使用 long long 记录结果。数据生成器已涵盖此情况。

在解决“层数最深叶子节点的和”时，核心挑战在于：我们无法在遍历结束前确定哪一层才是真正的“最深层”。

以下提供三个版本的代码：从直观的两遍扫描到标准的一遍层序遍历，再到竞赛级的常数优化版本。

版本一：深度优先搜索 (DFS) - 两遍扫描法

思路： 这是最符合直觉的暴力思路。

1. 第一遍 DFS：求出整棵树的最大深度 max_dep。
2. 第二遍 DFS：遍历整棵树，只累加深度等于 max_dep 的节点权值。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 10005;

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

int max_dep = 0;
long long ans = 0;

// 第一遍：找最大深度
void get_depth(int u, int d) {
    if (u == 0) return;
    max_dep = max(max_dep, d);
    get_depth(tree[u].l, d + 1);
    get_depth(tree[u].r, d + 1);
}

// 第二遍：累加最深层
void get_sum(int u, int d) {
    if (u == 0) return;
    if (d == max_dep) {
        ans += tree[u].v;
    }
    get_sum(tree[u].l, d + 1);
    get_sum(tree[u].r, d + 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;
    }

    get_depth(1, 1);
    get_sum(1, 1);

    cout << ans << endl;
    return 0;
}

版本二：广度优先搜索 (BFS) - 一遍层序法（标准推荐）

思路： 利用 BFS 按层遍历的特性。每进入新的一层，我们就刷新一次累加器 ans。当遍历结束时，ans 存储的自然就是最后一层的和。

#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);
    long long last_level_sum = 0;

    while (!q.empty()) {
        int sz = q.size();
        last_level_sum = 0; // 关键点：每处理新的一层，重置该层之和

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

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

    // 循环结束时，last_level_sum 存储的是最后一层的累加结果
    printf("%lld\n", last_level_sum);

    return 0;
}

版本三：竞赛最优复杂度版本 (静态队列 + DFS 一遍过)

思路： 在 DFS 过程中动态维护最大深度。如果发现更深的层，直接抛弃之前的累加值，重新开始。这是常数最小且逻辑最精练的写法。

#include <cstdio>

// 手写快读优化 IO
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 max_d = 0;
long long sum = 0;

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

    if (d > max_d) {
        // 关键点：发现更深的一层，更新最大深度，重置总和为当前节点值
        max_d = d;
        sum = tree[u].v;
    } else if (d == max_d) {
        // 关键点：处于当前已知的最深层，累加
        sum += tree[u].v;
    }

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

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

    dfs(1, 1);

    printf("%lld\n", sum);
    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 所有版本：每个节点都只被访问 1 次（版本一访问 2 次，但常数项不改变阶数）。
   • 结论：时间复杂度为 $O(N)$。对于 $N=10^4$，运行时间极短（<10ms）。

2. 空间复杂度分析：

   • 存储空间：静态数组存储树结构占用 $O(N)$。
   • 辅助空间：
     • BFS 版本：队列在最坏情况下（满二叉树底层）需要存储约 $N/2$ 个节点，空间 $O(N)$。
     • DFS 版本：递归调用消耗系统栈空间。最坏情况下（树退化成链）深度为 $N$，空间 $O(N)$。
   • 结论：总空间复杂度为 $O(N)$。

时间复杂度优化建议

1. IO 瓶颈：在 $N$ 很大时，$O(N)$ 的算法性能瓶颈通常在 cin 或 scanf。使用手写 getchar() 快速读入可以显著缩短耗时。
2. 遍历次数：版本三比版本一少了一次整树遍历，在数据规模极大时（如 $10^6$）会有明显优势。
3. 减少动态开辟：避免使用 std::vector<vector<int>> 这种结构，静态数组 struct Node tree[MAXN] 对缓存更友好。

关键点总结 (易错点)

1. 重置逻辑：

   • 使用 BFS 时，必须在 while 内部第一行重置 level_sum。
   • 使用 DFS 一遍过时，必须在 d > max_d 时重新赋值而不是累加。

2. 数据溢出：

   • 虽然节点权值是 int，但如果最深层节点非常多，和可能超过 $2^{31}-1$。建议养成求和变量使用 long long 的习惯。

3. 节点编号 0 的含义：

   • 在静态建树中，0 代表空节点。在递归或入队前一定要判断 u != 0，否则会引发非法内存访问（访问 tree[0]）。

4. $N=0$ 或 $N=1$：

   • NOI 题目常有此类边界测试。在编写代码时，先确定根节点是否存在。版本三中的 if (n <= 0) return 0; 是一种安全的编程习惯。