这是一份针对NOI/NOIP竞赛辅导的题解，包含从暴力直观解法到防溢出优化解法的完整演进过程。代码均符合C++14标准，包含完整的输入输出框架。

解题核心难点回顾

1. 完全二叉树索引：左孩子索引 $= 2 \times \text{父索引}$，右孩子索引 $= 2 \times \text{父索引} + 1$。
2. 数据溢出陷阱：虽然 $N \le 3000$，但如果是单链表形态，深度可达3000。直接计算索引会达到 $2^{3000}$，远超 unsigned long long 范围。

版本一：朴素BFS（直观但依赖特定特性）

思路： 最直观的想法是使用广度优先搜索（BFS），记录每个节点的绝对索引。 每一层的宽度 = 队尾节点索引 - 队首节点索引 + 1。

为什么它能通过？（特殊说明） 在C++中，unsigned long long 具有自然溢出（Mod $2^{64}$） 的特性。 即使 $A$ 和 $B$ 都溢出了（变成了很小的数），只要它们的实际差值在 $2^{64}$ 范围内，A - B 的计算结果依然是正确的（基于补码运算规则）。 但在教学中，我们不建议初学者完全依赖这种“溢出特性”，因为这容易掩盖算法设计的缺陷，且在其他语言（如Python/Java）中可能报错。

代码实现：

/* 
 * 版本一：朴素BFS (依赖 unsigned long long 自然溢出特性)
 * 优点：代码逻辑最简单，易于理解层序遍历
 * 缺点：如果是 signed long long 则会溢出导致未定义行为
 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 定义树的存储结构（静态数组模拟指针）
struct Node {
    int left = 0;
    int right = 0;
};

// 全局数组存储树，索引从1开始
const int MAXN = 3005;
Node tree[MAXN];

// 定义队列元素：{节点编号, 对应的堆索引}
struct QItem {
    int u;
    unsigned long long index; // 必须使用 unsigned long long
};

int main() {
    // 提升cin/cout速度，NOI标配
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0; // 读取节点数

    // 读取树结构
    // 输入格式：第i行代表节点i的左孩子和右孩子
    for (int i = 1; i <= n; ++i) {
        cin >> tree[i].left >> tree[i].right;
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    queue<QItem> q;
    q.push({1, 1}); // 根节点入队，假设索引为1

    unsigned long long maxWidth = 0;

    while (!q.empty()) {
        int size = q.size();
        
        // 获取当前层最左和最右的索引
        // 注意：back()和front()在队列不为空时才安全
        unsigned long long leftIndex = q.front().index;
        unsigned long long rightIndex = q.back().index;
        
        // 更新最大宽度
        // 即使溢出，无符号减法在宽度不超过2^64时依然正确
        maxWidth = max(maxWidth, rightIndex - leftIndex + 1);

        // 处理当前层的所有节点
        for (int i = 0; i < size; ++i) {
            QItem curr = q.front();
            q.pop();

            // 左孩子入队：index * 2
            if (tree[curr.u].left != 0) {
                q.push({tree[curr.u].left, curr.index * 2});
            }
            // 右孩子入队：index * 2 + 1
            if (tree[curr.u].right != 0) {
                q.push({tree[curr.u].right, curr.index * 2 + 1});
            }
        }
    }

    cout << maxWidth << endl;

    return 0;
}

版本二：BFS + 索引重置优化（NOI 标准满分写法）

思路（时间复杂度优化建议）： 为了避免依赖“溢出特性”并处理超深树，我们使用相对索引。

• 核心观察：一层的宽度只取决于该层节点的相对距离。
• 优化操作：在遍历每一层时，将该层第一个节点的索引记为 base。该层所有节点的索引 $i$ 都重置为 $i - base$。
• 这样，每一层第一个节点的索引永远重置为 0（或1），保证后续计算子节点索引时数值不会无限膨胀。

代码实现：

/* 
 * 版本二：BFS + 索引重置 (标准最优解)
 * 技巧：每层开始时，将索引减去该层最小索引，防止数字无限增长
 * 复杂度：时间 O(N)，空间 O(N)
 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 3005;

struct Node {
    int left = 0;
    int right = 0;
};

Node tree[MAXN];

struct QItem {
    int u;
    unsigned long long index; 
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

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

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    queue<QItem> q;
    q.push({1, 1}); // 根节点索引为1

    unsigned long long maxWidth = 0;

    while (!q.empty()) {
        int size = q.size();
        
        // 【关键点1】记录当前层第一个节点的索引作为基准 (base)
        unsigned long long base_index = q.front().index;
        
        unsigned long long current_left = 0, current_right = 0;

        for (int i = 0; i < size; ++i) {
            QItem curr = q.front();
            q.pop();

            // 【关键点2】对索引进行“缩点”重置
            // 当前节点的相对索引 = 绝对索引 - 本层基准索引
            // 这样能保证每层的索引都从 0 开始增长，防止溢出
            unsigned long long normalized_idx = curr.index - base_index;

            // 记录当前层的最左和最右相对索引
            if (i == 0) current_left = normalized_idx;
            if (i == size - 1) current_right = normalized_idx;

            // 将下一层节点入队
            // 下一层的绝对索引基于当前的相对索引计算
            // 左孩子：2 * idx, 右孩子：2 * idx + 1
            if (tree[curr.u].left != 0) {
                q.push({tree[curr.u].left, normalized_idx * 2});
            }
            if (tree[curr.u].right != 0) {
                q.push({tree[curr.u].right, normalized_idx * 2 + 1});
            }
        }
        
        // 计算宽度
        maxWidth = max(maxWidth, current_right - current_left + 1);
    }

    cout << maxWidth << endl;

    return 0;
}

复杂度与优化分析（教学用）

1. 时间复杂度：

   • 分析：我们需要将每个节点入队和出队一次。在处理每个节点时，进行的减法、乘法和判断操作都是 $O(1)$ 的。
   • 结论：$O(N)$，其中 $N$ 是节点数。这是遍历树的理论下界，无法进一步在量级上优化。

2. 空间复杂度：

   • 分析：队列中最多同时存储一层的节点。在最坏情况（满二叉树）下，最后一层的节点数约为 $N/2$。
   • 结论：$O(N)$。

3. 为什么“索引重置”是安全的？

   • 题目保证最大宽度在 32 位整数范围内。
   • 即使树深 3000 层，只要每层都减去 base，那么索引值的大小只与当前层的宽度有关，而不会随着层数指数级累积。
   • $2 \times \text{Width}$ 对于 unsigned long long 来说非常安全。

版本三：DFS 解法（深度优先搜索）

思路： 虽然 BFS 更符合直觉，但 DFS 也可以解决。 我们需要一个数组 min_index[depth] 记录每一层第一次访问到的节点（即最左节点）的索引。 当我们后续再次来到该 depth 时（因为是先序遍历，后面来的一定在右边），用 curr_index - min_index[depth] + 1 更新该层的最大宽度。

注意：DFS写法在没有大数库的情况下，通常也需要利用 unsigned long long 的自然溢出特性，因为很难像 BFS 那样层层重置基准。

/* 
 * 版本三：DFS (深度优先搜索)
 * 适合：习惯递归思维的学生
 * 注意：必须依赖 unsigned long long 的溢出截断特性
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <map> 

using namespace std;

const int MAXN = 3005;

struct Node {
    int left, right;
};
Node tree[MAXN];

// 记录每一层最左边节点的索引
// Key: depth, Value: index
// 这里可以用 vector 替代 map 优化常数，因为 depth <= N
vector<unsigned long long> left_most; 
unsigned long long max_width = 0;

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

    // 如果是第一次到达该深度，说明这就是该层最左边的节点
    if (depth >= left_most.size()) {
        left_most.push_back(index);
    }

    // 计算当前节点到该层最左节点的距离
    // 利用无符号整数溢出特性：(Index - Base) 即使溢出也是正确差值
    unsigned long long current_width = index - left_most[depth] + 1;
    max_width = max(max_width, current_width);

    // 递归处理子节点
    // 注意：这里 index 可能会溢出，但只要差值正确即可
    dfs(tree[u].left, depth + 1, index * 2);
    dfs(tree[u].right, depth + 1, index * 2 + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    for (int i = 1; i <= n; ++i) {
        cin >> tree[i].left >> tree[i].right;
    }
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 根节点深度0，索引1
    dfs(1, 0, 1);

    cout << max_width << endl;

    return 0;
}

总结建议

在 NOI/NOIP 考场上，推荐使用 版本二 (BFS + 索引重置)。

• 理由 1：逻辑严密，不依赖平台相关的溢出行为（虽然C++ unsigned溢出是定义的，但显式处理更显功底）。
• 理由 2：BFS 天然适合处理“层”相关的问题，思维负担小，不容易写错。
• 理由 3：避免了递归可能带来的爆栈风险（虽然 3000 层通常不会爆栈，但在极端限制内存的题目中 BFS 更稳）。

这是一份完整的C++数据生成器代码。它包含了标准解法（Solver）和针对不同测试点（1~10）的数据生成逻辑。

数据生成器说明

1. 输入格式（NOI风格）：
   • 第一行包含一个整数 $N$，表示节点总数（节点编号 $1$ 到 $N$，根节点恒为 $1$）。
   • 接下来 $N$ 行，第 $i$ 行包含两个整数 $L_i, R_i$，分别代表第 $i$ 号节点的左孩子和右孩子的编号。如果不存在，则为 $0$。
2. 数据覆盖策略：
   • 1-2 (Small): 小规模随机数据，用于手算验证。
   • 3-4 (Complete): 完全二叉树/满二叉树，测试宽度的指数增长（在 $N$ 允许范围内）。
   • 5-6 (Chain/Deep): 极深的链状树（"单脉传"），测试深度导致的下标溢出问题（这是本题核心考点）。虽然宽度很小（1或2），但如果不做下标偏移优化，计算出的 index 会超过 long long。
   • 7-8 (Sparse/Zigzag): 稀疏的之字形树，测试非规律性的空节点处理。
   • 9-10 (Random/Max): 大规模随机数据，综合测试性能和鲁棒性。
3. 技术细节：
   • 使用了 unsigned long long 配合每层重置索引（index - base）的方法来计算标准答案，确保生成的 .out 文件绝对正确。
   • 使用了 std::mt19937 生成高质量伪随机数。

C++ 数据生成器代码

请将以下代码保存为 generator.cpp，编译运行后，当前目录下会生成 1.in/1.out 到 10.in/10.out。

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

using namespace std;

// ==========================================
// 全局配置
// ==========================================
const int TEST_CASE_COUNT = 10;
const int MAX_N = 3000; // 题目要求的最大节点数

// 定义树的结构用于存储
struct Node {
    int left = 0;
    int right = 0;
};

// ==========================================
// 标准解法 (Solver) - 用于生成 .out 文件
// ==========================================
// 逻辑：BFS + 下标重置优化，防止溢出
long long solve_width(int n, const vector<Node>& adj) {
    if (n == 0) return 0;
    
    // 队列存储 {节点编号, 当前层的相对下标}
    // 使用 unsigned long long 避免未定义行为，虽然有防溢出逻辑
    queue<pair<int, unsigned long long>> q;
    q.push({1, 1}); // 根节点，索引1
    
    unsigned long long max_width = 0;
    
    while (!q.empty()) {
        int size = q.size();
        unsigned long long level_min_index = q.front().second; // 当前层基准
        unsigned long long left = 0, right = 0;
        
        for (int i = 0; i < size; ++i) {
            pair<int, unsigned long long> curr = q.front();
            q.pop();
            
            int u = curr.first;
            // 核心技巧：减去当前层最小下标，防止深度过深导致的数据溢出
            unsigned long long idx = curr.second - level_min_index;
            
            if (i == 0) left = idx;
            if (i == size - 1) right = idx;
            
            if (adj[u].left != 0) {
                // 左孩子索引 = 父索引 * 2
                q.push({adj[u].left, idx * 2}); 
            }
            if (adj[u].right != 0) {
                // 右孩子索引 = 父索引 * 2 + 1
                q.push({adj[u].right, idx * 2 + 1});
            }
        }
        // 宽度定义
        max_width = max(max_width, right - left + 1);
    }
    
    return max_width;
}

// ==========================================
// 数据生成策略集合
// ==========================================

// 随机连接生成器
void gen_random(int n, vector<Node>& adj, mt19937& rng) {
    // 节点 1 是根，从 2 到 n 依次挂载到前面的节点上
    vector<int> nodes;
    nodes.push_back(1);
    
    for (int i = 2; i <= n; ++i) {
        // 随机选一个已存在的节点作为父节点
        uniform_int_distribution<int> dist(0, nodes.size() - 1);
        int parent_idx = dist(rng);
        int parent = nodes[parent_idx];
        
        // 尝试挂载到左或右
        bool done = false;
        // 简单的随机尝试，如果满了就找下一个，保证生成效率
        // 为了避免死循环，如果随机几次失败，就线性查找空位
        if (adj[parent].left == 0 && adj[parent].right == 0) {
             if (rng() % 2 == 0) adj[parent].left = i;
             else adj[parent].right = i;
        } else if (adj[parent].left == 0) {
            adj[parent].left = i;
        } else if (adj[parent].right == 0) {
            adj[parent].right = i;
        } else {
            // 父节点满了，重新选一个实际上比较慢，
            // 简单策略：遍历nodes找到第一个有空位的
            for(int u : nodes) {
                if(adj[u].left == 0) { adj[u].left = i; break; }
                if(adj[u].right == 0) { adj[u].right = i; break; }
            }
        }
        nodes.push_back(i);
    }
}

// 完全二叉树生成器 (测试宽度增长)
void gen_complete(int n, vector<Node>& adj) {
    for (int i = 1; i <= n; ++i) {
        if (2 * i <= n) adj[i].left = 2 * i;
        if (2 * i + 1 <= n) adj[i].right = 2 * i + 1;
    }
}

// 链状/深树生成器 (测试溢出陷阱)
// 这种树宽度很小，但深度极大，如果不处理下标溢出必挂
void gen_chain(int n, vector<Node>& adj, mt19937& rng) {
    int curr = 1;
    for (int i = 2; i <= n; ++i) {
        // 90%概率单传，10%概率分叉(增加一点干扰)
        if (rng() % 10 == 0 && i < n) { 
            // 制造一个小分叉然后迅速结束，保持整体深度
            adj[curr].left = i;
            adj[curr].right = i + 1;
            curr = i; // 继续沿着左边走
            i++; // 跳过刚才用的那个节点
        } else {
            // 随机走左或右
            if (rng() % 2 == 0) {
                adj[curr].left = i;
            } else {
                adj[curr].right = i;
            }
            curr = i;
        }
    }
}

// 稀疏宽树 (测试空节点处理)
// 根部只有左右两个长链，在底部汇聚，虽然N只有3000，但如果不限制深度，
// 在最底层的宽度可能超过int范围。
// 注意：题目保证答案在32位整数内，所以我们不能生成宽度超过2^31的树。
// 这里的生成策略是：在深度约20的地方开始横向扩展。
void gen_pyramid(int n, vector<Node>& adj, mt19937& rng) {
    // 前几层构建满二叉树，消耗约 1000 个节点
    int limit = min(n, 1023); // depth 10
    for(int i=1; i<=limit; ++i) {
        if(2*i <= limit) adj[i].left = 2*i;
        if(2*i+1 <= limit) adj[i].right = 2*i+1;
    }
    // 剩余节点随机挂载到底层
    vector<int> leaves;
    for(int i=limit/2; i<=limit; ++i) leaves.push_back(i);
    
    for(int i=limit+1; i<=n; ++i) {
        if(leaves.empty()) break;
        uniform_int_distribution<int> dist(0, leaves.size()-1);
        int p = leaves[dist(rng)];
        if(adj[p].left == 0) adj[p].left = i;
        else if(adj[p].right == 0) adj[p].right = i;
        else {
            // 满了就移除
            leaves.erase(leaves.begin() + dist(rng)); // 简单处理，非O(1)但N小
            i--; // 重试
        }
    }
}


// ==========================================
// 主程序
// ==========================================
int main() {
    mt19937 rng(1337); // 固定种子保证可复现

    for (int id = 1; id <= TEST_CASE_COUNT; ++id) {
        string in_file = to_string(id) + ".in";
        string out_file = to_string(id) + ".out";
        
        ofstream fin(in_file);
        ofstream fout(out_file);
        
        if (!fin || !fout) {
            cerr << "Error opening files for case " << id << endl;
            return 1;
        }

        int n;
        vector<Node> adj;

        // --- 设定参数 ---
        if (id <= 2) {
            // Case 1-2: 小数据
            n = (id == 1) ? 10 : 20;
            adj.resize(n + 1);
            gen_random(n, adj, rng);
        } 
        else if (id <= 4) {
            // Case 3-4: 完全二叉树/满二叉树
            n = (id == 3) ? 100 : 2047; // 2047是满二叉树节点数 (2^11 - 1)
            adj.resize(n + 1);
            gen_complete(n, adj);
        }
        else if (id <= 6) {
            // Case 5-6: 深链树 (Deep Chain) - 这里的宽度很小，但深度导致 index 爆炸
            n = (id == 5) ? 500 : 3000;
            adj.resize(n + 1);
            gen_chain(n, adj, rng);
        }
        else if (id <= 8) {
             // Case 7-8: 随机稀疏
             n = (id == 7) ? 1500 : 2500;
             adj.resize(n + 1);
             gen_random(n, adj, rng);
        }
        else {
            // Case 9-10: 金字塔型/底部密集
            n = 3000;
            adj.resize(n + 1);
            gen_pyramid(n, adj, rng);
        }

        // --- 写入输入文件 ---
        fin << n << endl;
        for (int i = 1; i <= n; ++i) {
            fin << adj[i].left << " " << adj[i].right << endl;
        }

        // --- 计算并写入输出文件 ---
        long long ans = solve_width(n, adj);
        fout << ans << endl;

        cout << "Generated Case " << id << ": N=" << n << ", Ans=" << ans << endl;
        
        fin.close();
        fout.close();
    }

    cout << "All test cases generated successfully." << endl;
    return 0;
}

验证点说明 (对应OI教学)

运行此生成器后，你会得到10组数据，它们分别测试了：

1. Test 1-2: 基础逻辑验证。学生可以用手画出树结构（因为 $N$ 很小），手动模拟 BFS 过程。
2. Test 3-4 (Complete Tree): 验证标准情况。如果 $N=2047$ (深度11)，最大宽度应为 $1024$。这是验证算法是否正确计算满层的最基本测试。
3. Test 5-6 (Deep Chain): 这是最关键的测试点。
   • 树高接近 $3000$。
   • 如果学生使用简单的 index * 2 而不进行减法重置，在第 $64$ 层左右就会发生 unsigned long long 溢出（或者 long long 变为负数）。
   • 如果学生使用了重置优化（idx - min_idx），则能正确通过，且计算出的宽度通常很小（1 或 2）。
4. Test 9-10 (Dense Bottom): 确保在节点较多且层数适中（不会溢出）的情况下，算法能正确处理中间有大量 null 或没有 null 的混合情况。

对应的解题代码读取部分 (供参考)

为了让你的学生能使用这些数据，你需要告诉他们输入代码的模板（对应上述生成器的格式）：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int left, right;
};

Node tree[3005]; // 静态数组存储树结构

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

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

    // 此处调用 widthOfBinaryTree 核心逻辑
    // root 节点下标为 1
    // ...
    
    return 0;
}