为了方便你创建 OJ 测试数据，我编写了一个基于 C++14 标准的自动化数据生成器。它采用了**迭代（非递归）**的方式构建树结构，能够处理 $N=10^5$ 规模的数据而不会爆栈，并涵盖了所有奇偶性、单调性以及边界情况。

1. 数据生成器设计思路

• 结构生成：使用 BFS 顺序分配父子关系，确保生成的一定是一棵连通的二叉树。
• 权值构造：
  • 偶数层：生成递增奇数序列（如 $1, 3, 5, \dots$）。
  • 奇数层：生成递减偶数序列（如 $10^6, 10^6-2, \dots$）。
• 错误注入：在非有效（Invalid）测试点中，随机选取节点修改其权值，破坏奇偶性或单调性。
• IO 效率：使用 std::vector 和 std::queue 配合 ofstream，生成速度快。

2. 数据生成器代码 (C++14)

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

using namespace std;

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

// ---------------- 核心算法：用于生成标准答案 (.out) ----------------
string solve(int n, const vector<Node>& tree) {
    if (n == 0) return "false";
    queue<pair<int, int>> q;
    q.push({1, 0}); // 节点编号, 层号

    vector<int> last_val(n + 1, -1);
    
    // 使用 BFS 进行层序遍历
    queue<int> node_q;
    queue<int> level_q;
    node_q.push(1);
    level_q.push(0);

    int cur_level = -1;
    int prev_v = -1;

    while (!node_q.empty()) {
        int u = node_q.front(); node_q.pop();
        int lev = level_q.front(); level_q.pop();
        int val = tree[u].v;

        // 换层处理
        if (lev != cur_level) {
            cur_level = lev;
            prev_v = (lev % 2 == 0) ? -1 : 1000001;
        }

        // 校验逻辑
        if (lev % 2 == 0) { // 偶数层：奇数且递增
            if (val % 2 == 0 || val <= prev_v) return "false";
        } else { // 奇数层：偶数且递减
            if (val % 2 != 0 || val >= prev_v) return "false";
        }
        prev_v = val;

        if (tree[u].l) { node_q.push(tree[u].l); level_q.push(lev + 1); }
        if (tree[u].r) { node_q.push(tree[u].r); level_q.push(lev + 1); }
    }
    return "true";
}

// ---------------- 随机数工具 ----------------
mt19937 rng(42);
int randInt(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

// ---------------- 树生成函数 ----------------
void make_tree(int n, bool is_valid, int type, vector<Node>& tree) {
    tree.assign(n + 1, {0, 0, 0});
    vector<int> levels(n + 1, 0);
    
    // 1. 构造拓扑结构 (BFS 顺序确保无环且连通)
    if (type == 1) { // 链状
        for (int i = 1; i < n; ++i) {
            tree[i].l = i + 1;
            levels[i+1] = levels[i] + 1;
        }
    } else { // 较平衡的树
        int head = 1, tail = 2;
        while (tail <= n) {
            if (tail <= n) { tree[head].l = tail; levels[tail] = levels[head] + 1; tail++; }
            if (tail <= n) { tree[head].r = tail; levels[tail] = levels[head] + 1; tail++; }
            head++;
        }
    }

    // 2. 构造权值
    vector<vector<int>> level_nodes(n);
    int max_l = 0;
    for(int i=1; i<=n; ++i) {
        level_nodes[levels[i]].push_back(i);
        max_l = max(max_l, levels[i]);
    }

    for (int l = 0; l <= max_l; ++l) {
        int base;
        if (l % 2 == 0) { // 偶数层：奇数递增
            base = 1;
            for (int u : level_nodes[l]) {
                tree[u].v = base;
                base += 2 + randInt(0, 2);
            }
        } else { // 奇数层：偶数递减
            base = 1000000;
            for (int u : level_nodes[l]) {
                tree[u].v = base;
                base -= (2 + randInt(0, 2));
            }
        }
    }

    // 3. 注入错误
    if (!is_valid && n > 0) {
        int target = randInt(1, n);
        int l = levels[target];
        if (randInt(0, 1)) { // 破坏奇偶性
            if (l % 2 == 0) tree[target].v = 2; // 偶数层变偶数
            else tree[target].v = 1;           // 奇数层变奇数
        } else { // 破坏单调性
            tree[target].v = (l % 2 == 0) ? 1 : 1000000; 
        }
    }
}

void generate(int t) {
    string in_n = to_string(t) + ".in";
    string out_n = to_string(t) + ".out";
    ofstream fin(in_n);
    
    int n;
    bool valid = true;
    int type = 0; // 0: random, 1: chain

    if (t == 1) n = 1;
    else if (t == 2) n = 10;
    else if (t == 3) { n = 100000; type = 0; } // 大规模平衡
    else if (t == 4) { n = 100000; type = 1; } // 大规模长链
    else if (t == 5) { n = 100000; valid = false; } // 权值错误
    else if (t == 6) { n = 100000; valid = false; } // 单调性错误
    else if (t == 7) { n = 50000; valid = false; }
    else if (t == 8) { n = 80000; valid = true; }
    else if (t == 9) { n = 100000; valid = false; }
    else { n = 100000; valid = true; }

    vector<Node> tree;
    make_tree(n, valid, type, tree);

    fin << n << "\n";
    for (int i = 1; i <= n; ++i) {
        fin << tree[i].v << " " << tree[i].l << " " << tree[i].r << "\n";
    }
    fin.close();

    ofstream fout(out_n);
    fout << solve(n, tree) << endl;
    fout.close();
    cout << "Testcase " << t << " finished." << endl;
}

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

3. 测试点设计说明

4. 教练寄语

1. 文件大小控制：由于每行约 15-20 字节，$10^5$ 行对应约 1.8MB，10 个测试点虽然总计超 10MB，但单个输入文件严格控制在 2MB 以内，方便在各种 OJ 上传。
2. 抗爆栈建议：测试点 4 的深度达到了 $10^5$。如果学生使用递归 DFS 且没有在编译选项中开大栈空间（-Wl,--stack=...），一定会发生段错误（Segmentation Fault）。这能有效引导学生学习 BFS 或非递归写法。
3. 单调性细节：生成器在制造“严格递增/递减”时，随机增加了偏移量（2 + randInt(0, 2)），这能有效防止学生用非严格比较（如 < vs <=）混过去。

在处理“奇偶树”这类涉及层级约束的题目时，最稳健的方法是广度优先搜索 (BFS)，因为它能让我们在处理每一层节点时，拥有该层完整的上下文信息（如当前是第几层、上一个节点的值是多少）。

以下提供三个版本的 C++ 代码：从基础的 std::queue 实现，到深度优先搜索 (DFS) 的另一种视角，最后是 NOI 竞赛中最追求常数效率的优化版本。

版本一：标准 BFS 层序遍历（最推荐，逻辑最清晰）

思路：使用 std::queue 按层遍历。在进入每一层时，先判断当前层号的奇偶性，并设定对应的初始比较值 prev。

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

using namespace std;

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

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

    queue<int> q;
    q.push(1);
    int level = 0;

    while (!q.empty()) {
        int sz = q.size();
        // prev 初始化：偶数层递增则设为极小，奇数层递减则设为极大
        int prev = (level % 2 == 0) ? 0 : 1000001;

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

            if (level % 2 == 0) { // 偶数层：必须是奇数且严格递增
                if (cur % 2 == 0 || cur <= prev) return false;
            } else { // 奇数层：必须是偶数且严格递减
                if (cur % 2 != 0 || cur >= prev) return false;
            }
            prev = cur; // 更新上一个节点的值

            if (tree[u].l) q.push(tree[u].l);
            if (tree[u].r) q.push(tree[u].r);
        }
        level++;
    }
    return true;
}

int main() {
    // 竞赛优化：加速cin
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    if (solve()) cout << "true" << endl;
    else cout << "false" << endl;
    
    return 0;
}

版本二：DFS 深度优先遍历（另一种思维）

思路：使用 DFS 遍历，并维护一个全局数组 last_val[depth] 记录每一层上一次访问到的节点值。 注意：在 NOI 中，DFS 虽然代码短，但如果树退化成链且 $N=10^5$，默认系统栈可能会溢出（本题建议在考场上手动增加栈空间）。

#include <iostream>
#include <vector>

using namespace std;

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

int last_val[MAXN]; // 记录每一层上一个访问的节点值
bool failed = false;

void dfs(int u, int dep) {
    if (u == 0 || failed) return;

    int cur = tree[u].v;
    // 1. 奇偶性检查
    if (dep % 2 == 0) { // 偶数层要求奇数
        if (cur % 2 == 0) { failed = true; return; }
    } else { // 奇数层要求偶数
        if (cur % 2 != 0) { failed = true; return; }
    }

    // 2. 单调性检查
    if (last_val[dep] != -1) {
        if (dep % 2 == 0) { // 偶数层严格递增
            if (cur <= last_val[dep]) { failed = true; return; }
        } else { // 奇数层严格递减
            if (cur >= last_val[dep]) { failed = true; return; }
        }
    }
    last_val[dep] = cur;

    // 3. 递归：由于是层序单调，DFS必须先左后右
    dfs(tree[u].l, dep + 1);
    dfs(tree[u].r, dep + 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;
        last_val[i-1] = -1; // 初始化
    }

    dfs(1, 0);

    if (failed) cout << "false" << endl;
    else cout << "true" << endl;
    return 0;
}

版本三：NOI 竞赛级优化（数组模拟队列 + 快读）

思路：在 $N=10^5$ 时，频繁的 std::queue 入队和 cin 读入可能消耗过多时间。手写快速读入和静态数组队列能显著压低耗时。

#include <cstdio>

// 手写快读：极致速度
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x;
}

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

int q[MAXN]; // 静态队列

int main() {
    int n = read();
    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;
    int level = 0;

    while (head < tail) {
        int sz = tail - head;
        int prev = (level % 2 == 0) ? 0 : 1000001;

        while (sz--) {
            int u = q[head++];
            int cur = tree[u].v;

            // 核心逻辑判断
            if (level % 2 == 0) {
                if (!(cur & 1) || cur <= prev) { printf("false\n"); return 0; }
            } else {
                if ((cur & 1) || cur >= prev) { printf("false\n"); return 0; }
            }
            prev = cur;

            if (tree[u].l) q[tail++] = tree[u].l;
            if (tree[u].r) q[tail++] = tree[u].r;
        }
        level++;
    }

    printf("true\n");
    return 0;
}

复杂度分析思考过程

1. 时间复杂度：

   • 遍历过程：每个节点编号仅入队和出队各 1 次，每个节点只被访问一次。
   • 判断逻辑：奇偶性和大小比较均为 $O(1)$。
   • 结论：总时间复杂度为 $O(N)$。对于 $10^5$ 的量级，即使在较慢的评测机上，版本三通常也能在 20ms 内运行完毕。

2. 空间复杂度：

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

时间复杂度优化建议

• 位运算：判断奇偶性时，(cur & 1) 比 cur % 2 != 0 稍快（虽然编译器通常会自动优化）。
• 尽早退出 (Early Exit)：一旦发现不满足奇偶树条件的节点，立刻结束程序，不要继续遍历后续层。
• 避免大量小内存申请：在 NOI 竞赛中，使用 std::vector<int> levelNodes 存储每一层再遍历会比直接在队列中处理慢，因为涉及到多次内存分配。

关键点总结（读题眼）

• “严格” (Strictly)：
  • 看到这两个字，代码中绝对不能写 <= 或 >=。平局也是不合法的。
• “层号从 0 开始”：
  • 这决定了第一层是偶数层（Odd values）。如果题目改从 1 开始，所有逻辑都要反过来。
• “1 <= n <= 10^5”：
  • 这种规模暗示了 $O(N \log N)$ 或 $O(N)$ 的解法。同时要警惕 DFS 的栈深度。
• “1 <= val <= 10^6”：
  • 值不为 0，说明我们可以用 0 作为严格递增序列的初始 prev。