阿西莫夫的解题指南

这道题是二叉树最基础的“骨架练习”。

1. 存储结构： 由于 $N$ 可达 $10^5$，我们通常使用结构体数组或两个数组来存储树。

   struct Node {
       int left;
       int right;
   } tree[100005];
   

   tree[i].left 就代表 $i$ 号节点的左孩子 ID。

2. 核心算法：DFS（递归） 二叉树是天然的递归结构。

   • 求大小 (Size)： Size(u) = 1 + Size(u.left) + Size(u.right) （如果不为空，否则为 0）
   • 求深度 (Depth)： Depth(u) = 1 + max(Depth(u.left), Depth(u.right)) （如果不为空，否则为 0）

   我们可以在一次 DFS 遍历中同时计算这两个值，或者分开写两个函数。

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

/**
 * 题目: 细胞分化的“谱系树” (The Cell Lineage Tree)
 * 作者: Isaac Asimov (AI)
 * 知识点: 二叉树存储, 递归 (DFS), 树的深度与大小
 */

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max

using namespace std;

const int MAXN = 100005;

// 定义二叉树节点结构
struct Node {
    int left;
    int right;
} tree[MAXN];

// 全局变量记录最大深度和总节点数
// 虽然题目已给 N，但我们可以通过遍历验证节点数 (作为练习)
// 实际上总节点数就是输入的 N，但为了演示树的遍历，我们还是算一遍
int max_depth = 0;
int total_nodes = 0;

// DFS 函数: 计算以 u 为根的子树深度和大小
// 返回值: 该子树的深度
int dfs(int u) {
    // 递归基: 如果节点不存在 (编号为0)，深度为0
    if (u == 0) return 0;

    // 统计节点数 (前序遍历位置)
    total_nodes++;

    // 递归计算左右子树的深度
    int l_depth = dfs(tree[u].left);
    int r_depth = dfs(tree[u].right);

    // 当前节点的深度 = 1 + max(左深, 右深)
    return 1 + max(l_depth, r_depth);
}

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

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

    // 读入树的结构
    // 下标从 1 开始
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].left >> tree[i].right;
    }

    // 从根节点 (1号) 开始遍历
    int depth = dfs(1);

    // 输出: 总节点数 (实际上必然等于 n), 最大深度
    cout << total_nodes << " " << depth << endl;

    return 0;
}

数据生成器 (Generator)

生成一棵合法的树稍微有点技巧。我们需要确保不出现环，且每个节点的父亲唯一。 常用的生成方法是：

1. 建立一个节点池，初始只有根节点 1。
2. 依次生成节点 $2 \dots N$，每次随机选择池中的一个节点作为父亲，挂在它的左边或右边（如果空闲）。

请保存为 gen_tree.cpp 并运行。

/**
 * Project: Cell Lineage Tree (Tree Data Generator)
 * Author: Isaac Asimov (AI)
 */

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

using namespace std;

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

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

        cnt = 0;
        int d = get_depth(1);
        cout << cnt << " " << d << 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);
}

struct GenNode {
    int id;
    int l = 0, r = 0;
    // 记录还有几个空位 (0, 1, 2)
    int free_slots = 2; 
};

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

    int n;
    // 规模设定
    if (case_id <= 3) n = 5 + case_id * 2;
    else if (case_id <= 7) n = rand_int(100, 500);
    else n = rand_int(50000, 100000);

    fout << n << endl;

    // 树的构建信息：vec[i] 存储 i 号节点的左右孩子
    vector<pair<int, int>> tree_struct(n + 1, {0, 0});

    // 构造策略
    if (case_id == 5) {
        // Case 5: 链状结构 (退化成链表) 深度 = N
        for (int i = 1; i < n; i++) {
            // 随机连左还是连右
            if (rand_int(0, 1)) tree_struct[i].first = i + 1;
            else tree_struct[i].second = i + 1;
        }
    }
    else if (case_id == 6) {
        // Case 6: 满二叉树倾向 (深度最小 logN)
        // 父节点 i 的孩子是 2*i 和 2*i+1
        for (int i = 1; i <= n; i++) {
            if (2 * i <= n) tree_struct[i].first = 2 * i;
            if (2 * i + 1 <= n) tree_struct[i].second = 2 * i + 1;
        }
    }
    else {
        // 随机生成树
        // 方法：prufer序列太复杂，用简单的“挂载法”
        // 维护一个可用的父节点列表 (有空位的节点)
        vector<int> available_parents;
        available_parents.push_back(1);
        
        // 节点 2 到 N 依次找爸爸
        // 为了让树比较随机，随机打乱节点编号映射，或者直接按顺序挂
        // 这里为了简单，节点 i 挂在 [1...i-1] 中的某个节点下
        
        // 这里的 available_parents 存的是还没满的节点
        // 为了避免总是挂在前面导致树太扁或太深，我们可以随机从 available 中取
        
        for (int i = 2; i <= n; i++) {
            // 随机选一个爹
            int idx = rand_int(0, available_parents.size() - 1);
            int parent = available_parents[idx];
            
            // 决定挂左边还是右边
            bool attach_left = false;
            if (tree_struct[parent].first == 0 && tree_struct[parent].second == 0) {
                // 两边都空，随机选
                attach_left = rand_int(0, 1);
            } else if (tree_struct[parent].first == 0) {
                attach_left = true;
            } else {
                attach_left = false;
            }
            
            if (attach_left) tree_struct[parent].first = i;
            else tree_struct[parent].second = i;
            
            // 如果这个爹满了，从可用列表中移除
            if (tree_struct[parent].first != 0 && tree_struct[parent].second != 0) {
                // 交换到末尾删除，O(1)
                available_parents[idx] = available_parents.back();
                available_parents.pop_back();
            }
            
            // 新节点也是潜在的爹
            available_parents.push_back(i);
        }
    }

    // 输出
    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 Cell Lineage 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. 递归的艺术： “细胞分裂”是递归最好的隐喻。一个细胞分裂成两个，这两个又各自开启新的分裂旅程。代码中的 dfs 函数正是这一过程的数学描述。
2. 树的形态： 在数据生成器中，我特意设计了链状树（Case 5）和满二叉树（Case 6）。
   • 链状树深度最大（$N$），递归可能导致栈溢出（Stack Overflow）（如果在系统栈较小的环境）。
   • 满二叉树深度最小（$\log N$）。 这让学生直观地感受到树的“平衡性”对算法性能的影响。

通过这道题，学生不仅学会了如何操作二叉树，还能在脑海中建立起生命演化的树状图景。