阿西莫夫的解题指南

这道题是 层序遍历（Level-Order Traversal） 的标准模板题。

1. 数据结构：使用 std::queue。
2. 算法逻辑：
   • 初始将根节点 1 入队。
   • 开始循环：每次循环处理一整层的节点。
   • 关键技巧：在 while 循环内部，再写一个 for 循环，次数为 当前队列的大小 (q.size())。
     • 这个技巧能保证我们在这一轮里处理完当前这一层的所有节点，并将它们的子节点（下一层）加入队列。
     • 每完成一轮 for 循环，代数 level 加 1。
   • 当 level == K 时，队列里剩下的就是第 $K$ 代的所有节点，直接输出即可。

C++ 标准解答 (NOIP C++14)

/**
 * 题目: 细菌菌落的“代际普查” (BFS Level Order)
 * 作者: Isaac Asimov (AI)
 * 知识点: 二叉树, BFS (std::queue)
 */

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

using namespace std;

const int MAXN = 100005;

// 存储树结构
struct Node {
    int left;
    int right;
} tree[MAXN];

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    // 读入树
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].left >> tree[i].right;
    }

    // BFS 初始化
    queue<int> q;
    q.push(1); // 根节点入队

    int current_generation = 1; // 当前是第1代

    // 开始 BFS
    while (!q.empty()) {
        // 如果当前代数已经是 K，那么队列里的就是我们要找的
        if (current_generation == k) {
            bool first = true;
            while (!q.empty()) {
                if (!first) cout << " ";
                cout << q.front();
                q.pop();
                first = false;
            }
            cout << endl;
            return 0; // 任务完成，结束程序
        }

        // 核心技巧：只处理当前这一层的节点
        int level_size = q.size();
        for (int i = 0; i < level_size; i++) {
            int u = q.front();
            q.pop();

            // 将下一代（子节点）入队
            if (tree[u].left != 0) q.push(tree[u].left);
            if (tree[u].right != 0) q.push(tree[u].right);
        }

        // 这一层处理完了，进入下一代
        current_generation++;
    }

    // 如果队列空了还没到第 K 代
    cout << "Empty" << endl;

    return 0;
}

数据生成器 (Generator)

生成器会构造各种形态的二叉树（满树、稀疏树、深树），并随机指定一个目标代数 $K$。

请保存为 gen_bfs.cpp 并运行。

/**
 * Project: Bacterial Generation (BFS Data Generator)
 * Author: Isaac Asimov (AI)
 */

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

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
struct Node { int l, r; };
class Solution {
    vector<Node> tr;
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n, k;
        cin >> n >> k;
        tr.assign(n + 1, {0, 0});
        for(int i=1; i<=n; i++) cin >> tr[i].l >> tr[i].r;

        queue<int> q;
        q.push(1);
        int level = 1;
        bool found = false;

        while(!q.empty()) {
            if (level == k) {
                found = true;
                bool first = true;
                while(!q.empty()) {
                    if(!first) cout << " ";
                    cout << q.front();
                    q.pop();
                    first = false;
                }
                cout << endl;
                break;
            }
            int sz = q.size();
            for(int i=0; i<sz; i++) {
                int u = q.front(); q.pop();
                if(tr[u].l) q.push(tr[u].l);
                if(tr[u].r) q.push(tr[u].r);
            }
            level++;
        }

        if (!found) cout << "Empty" << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n, k;
    if (case_id <= 3) n = 10;
    else if (case_id <= 7) n = rand_int(100, 1000);
    else n = rand_int(50000, 100000);

    vector<pair<int, int>> tree_struct(n + 1, {0, 0});
    vector<int> available_parents;
    available_parents.push_back(1);

    // 构造树
    for (int i = 2; i <= n; i++) {
        int idx = rand_int(0, available_parents.size() - 1);
        int p = available_parents[idx];

        if (tree_struct[p].first == 0 && tree_struct[p].second == 0) {
            if (rand_int(0, 1)) tree_struct[p].first = i;
            else tree_struct[p].second = i;
        } else if (tree_struct[p].first == 0) {
            tree_struct[p].first = i;
        } else {
            tree_struct[p].second = i;
        }

        if (tree_struct[p].first != 0 && tree_struct[p].second != 0) {
            available_parents[idx] = available_parents.back();
            available_parents.pop_back();
        }
        available_parents.push_back(i);
    }

    // 决定 K 的值
    // Case 5: 浅层测试 (K很小)
    if (case_id == 5) k = 2;
    // Case 6: 越界测试 (K很大，超过深度)
    else if (case_id == 6) k = n + 5; 
    else {
        // 估算一下深度，大概 logN 到 N 之间
        // 随机取一个中间值
        k = rand_int(1, min(n, 50)); // 树如果不深，50可能会越界，正好测试 Empty
    }

    fout << n << " " << k << endl;
    for (int i = 1; i <= n; i++) {
        fout << tree_struct[i].first << " " << tree_struct[i].second << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Bacterial Census Data ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的点评

1. 分层思想： 这段 BFS 代码中 int level_size = q.size(); 这一行是灵魂所在。它将连续的队列流切分成了离散的“代（Generation）”。没有这行代码，虽然也能遍历树，但你就不知道谁是第几代的了。
2. 生物学视角： 从根节点出发，无论树长得多么歪七扭八，同一深度的节点在演化时间轴上是处于同一时刻的。这正是“系统发生树（Phylogenetic Tree）”定年的基础逻辑。