这是一个用于生成 P11378 [GESP202412 七级] 燃烧 题目测试数据的 C++ 程序。

⚙️ 功能特点

1. 覆盖全子任务：严格按照题目要求生成 $N \le 10, 100, 10^5$ 的各类数据。
2. 安全性优化：为了防止在生成大规模链状数据（如 $N=10^5$ 的长链）时发生栈溢出 (Stack Overflow)，内置的求解器 (Solver) 采用了非递归的迭代写法（基于权值排序的 DP）。这保证了在任何本地环境下都能稳定生成 .out 文件。
3. 场景多样化：
   • 基础数据：随机树、随机权值。
   • 边界数据：权值全部相等（答案为1）、星状图、链状图。
   • 压力数据：$N=10^5$ 的长链、特定顺序权值（递增/递减）以测试最长路径。

📄 数据生成器代码 (Generator)

将以下代码保存为 generator.cpp，编译运行即可在当前目录下生成 1.in/1.out ~ 10.in/10.out。

/**
 * P11378 [GESP202412 七级] 燃烧 - 数据生成器
 * 
 * 包含：
 * 1. Solver: 迭代式 DP 解法 (防爆栈)，用于生成 .out
 * 2. Generator: 覆盖各类树形结构和权值分布的生成策略
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <random>
#include <ctime>
#include <string>
#include <numeric> // for iota

using namespace std;

// ==========================================
// Part 1: 高性能迭代式 Solver (用于生成 .out)
// ==========================================
// 解释：标准解法是递归 DFS，但在生成器中为了防止 N=10^5 的长链导致
// 本地栈溢出，这里改用基于“权值排序”的迭代 DP。
// 原理：火只能从大权值流向小权值。如果我们按权值从小到大处理节点，
// 处理到节点 u 时，所有比 u 小的邻居 v 的 DP 值一定已经计算完毕。

namespace Solver {
    const int MAXN = 100005;
    int a[MAXN];
    vector<int> adj[MAXN];
    int dp[MAXN];
    
    // 用于排序的结构体
    struct Node {
        int id;
        int val;
        // 权值小的排前面
        bool operator<(const Node& other) const {
            return val < other.val;
        }
    };
    Node nodes[MAXN];

    int solve(int n, const vector<int>& weights, const vector<pair<int,int>>& edges) {
        // 1. 初始化
        for(int i=1; i<=n; ++i) {
            adj[i].clear();
            dp[i] = 0;
            a[i] = weights[i-1];
            nodes[i] = {i, a[i]};
        }
        
        for(auto& e : edges) {
            adj[e.first].push_back(e.second);
            adj[e.second].push_back(e.first);
        }

        // 2. 排序：按权值从小到大处理
        // 这样保证处理 u 时，所有 a[v] < a[u] 的 v 都已经算好了
        sort(nodes + 1, nodes + n + 1);

        int max_ans = 0;

        // 3. 迭代 DP
        for(int i = 1; i <= n; ++i) {
            int u = nodes[i].id; // 当前处理的节点编号
            dp[u] = 1; // 初始只有自己
            
            for(int v : adj[u]) {
                // 状态转移：累加严格小于自己的邻居
                if(a[v] < a[u]) {
                    dp[u] += dp[v];
                }
            }
            max_ans = max(max_ans, dp[u]);
        }
        
        return max_ans;
    }
}

// ==========================================
// Part 2: 数据生成器 Generator
// ==========================================

mt19937 rng(time(0));

int random_int(int l, int r) {
    if (l > r) return l;
    return uniform_int_distribution<int>(l, r)(rng);
}

// 生成树的边
vector<pair<int, int>> gen_tree(int n, string type) {
    vector<pair<int, int>> edges;
    if (type == "line") {
        // 链状：1-2-3-...-n
        // 为了避免总是顺序连，打乱节点编号映射
        vector<int> p(n);
        iota(p.begin(), p.end(), 1);
        shuffle(p.begin(), p.end(), rng);
        for(int i=0; i<n-1; ++i) {
            edges.push_back({p[i], p[i+1]});
        }
    } 
    else if (type == "star") {
        // 菊花图：1 连 2...n
        for(int i=2; i<=n; ++i) {
            edges.push_back({1, i});
        }
    } 
    else if (type == "binary") {
        // 类似二叉树/深树：节点 i 挂在 [i/2, i-1] 之间
        // 节点编号稍微打乱一下避免规律太明显
        vector<int> p(n);
        iota(p.begin(), p.end(), 1);
        // 不完全打乱，保持一定层次性，或者直接生成后打乱边
        for(int i=1; i<n; ++i) {
            // p[i] (即 i+1 号点) 连向 p[random(i/2, i-1)]
            int parent_idx = random_int(i/2, i-1); 
            edges.push_back({p[parent_idx], p[i]});
        }
    }
    else { // random
        // 标准随机树生成：i 连接到 1..i-1 中的一个
        for(int i=2; i<=n; ++i) {
            int p = random_int(1, i-1);
            edges.push_back({p, i});
        }
    }
    return edges;
}

void generate_file(int file_id) {
    string in_name = to_string(file_id) + ".in";
    string out_name = to_string(file_id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);
    
    int n;
    vector<int> a; // 权值
    string tree_type = "random";
    
    // ================= 配置策略 =================
    
    // --- Subtask 1: N <= 10 ---
    if (file_id == 1) {
        n = 8;
        tree_type = "random";
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 20));
    }
    else if (file_id == 2) {
        n = 10;
        tree_type = "line"; // 链
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 20));
    }
    
    // --- Subtask 2: N <= 100 ---
    else if (file_id == 3) {
        n = 100;
        tree_type = "random";
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 1000));
    }
    else if (file_id == 4) {
        n = 100;
        tree_type = "star"; // 菊花
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 1000));
    }
    
    // --- Subtask 3: N <= 10^5 ---
    else if (file_id == 5) {
        // Case 5: 长链，权值严格递增 (1...N)
        // 实际上是一条单行道，从 N 出发能烧回 1，答案应为 N
        n = 100000;
        tree_type = "line";
        // 这里特殊构造：我们手动生成边，不使用 gen_tree 的随机 line
        // 确保是一条有序链 1-2-3...-N，且 a[i] = i
        // 这样 1<2<3...，火只能从 i+1 传给 i
        a.resize(n);
        iota(a.begin(), a.end(), 1); // 1, 2, ..., N
        
        vector<pair<int, int>> edges;
        for(int i=1; i<n; ++i) edges.push_back({i, i+1});
        
        // 写入文件逻辑下移
        fin << n << "\n";
        for(int i=0; i<n; ++i) fin << a[i] << (i==n-1?"":" ");
        fin << "\n";
        // 打乱边顺序
        shuffle(edges.begin(), edges.end(), rng);
        for(auto& e : edges) fin << e.first << " " << e.second << "\n";
        
        fout << Solver::solve(n, a, edges) << "\n";
        cout << "Generated Case " << file_id << " (N=" << n << ", Ordered Line)" << endl;
        fin.close(); fout.close(); return;
    }
    else if (file_id == 6) {
        // Case 6: 菊花图，中心 1 号点权值最大，四周随机
        // 答案应为 N
        n = 100000;
        tree_type = "star";
        a.resize(n);
        a[0] = 1000000; // 1号点权值最大
        for(int i=1; i<n; ++i) a[i] = random_int(1, 999999);
    }
    else if (file_id == 7) {
        // Case 7: 菊花图，中心 1 号点权值最小
        // 中心烧不到任何人，任何人烧到中心就停。答案应很小。
        n = 100000;
        tree_type = "star";
        a.resize(n);
        a[0] = 1; 
        for(int i=1; i<n; ++i) a[i] = random_int(2, 1000000);
    }
    else if (file_id == 8) {
        // Case 8: 所有权值相等
        // 任何火都传不出去，答案应为 1
        n = 100000;
        tree_type = "random";
        a.assign(n, 666);
    }
    else if (file_id == 9) {
        // Case 9: 类二叉树/深树，随机权值
        n = 100000;
        tree_type = "binary";
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 1000000));
    }
    else { // file_id == 10
        // Case 10: 完全随机压力测试
        n = 100000;
        tree_type = "random";
        for(int i=0; i<n; ++i) a.push_back(random_int(1, 1000000));
    }
    
    // ================= 生成数据 =================
    
    vector<pair<int, int>> edges = gen_tree(n, tree_type);
    
    // 写入输入文件
    fin << n << "\n";
    for(int i=0; i<n; ++i) {
        fin << a[i] << (i==n-1?"":" ");
    }
    fin << "\n";
    
    // 打乱边的输出顺序，增加数据真实性
    shuffle(edges.begin(), edges.end(), rng);
    for(auto& e : edges) {
        // 随机交换 u, v 输出
        if (random_int(0, 1)) fin << e.first << " " << e.second << "\n";
        else fin << e.second << " " << e.first << "\n";
    }
    
    // 计算并写入输出文件
    int ans = Solver::solve(n, a, edges);
    fout << ans << "\n";
    
    cout << "Generated Case " << file_id << " (N=" << n << ")" << endl;
    
    fin.close();
    fout.close();
}

int main() {
    // 优化生成速度
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    for (int i = 1; i <= 10; ++i) {
        generate_file(i);
    }
    
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

🎯 数据测试点设计

测试点	$N$	结构类型	权值分布	测试目的
1	8	随机树	随机	Subtask 1 基础测试
2	10	链状		Subtask 1 边界测试
3	100	随机树		Subtask 2 基础测试
4		菊花图		Subtask 2 结构测试
5	$10^5$	有序链	$1 \to 2 \to \dots \to N$	极限路径，火应能烧满全图，测栈深度与算法正确性
6		菊花图	中心最大	广度优先传播测试，答案应为 $N$
7			中心最小	无法传播测试，答案应很小
8		随机树	全部相等	严格小于条件测试，答案应为 $1$
9		深树(类二叉)	随机	深层递归/传播测试
10		随机树		综合压力测试

🛠️ 编译与运行

确保你的编译器支持 C++11 或更高版本（现代编译器均支持）。

g++ generator.cpp -o generator -O2
./generator

运行大约需要 1-2 秒即可生成全部 10 组数据。由于使用了迭代式 DP，即使在默认栈大小较小的 Windows 环境下也不会崩溃。

这是一份符合 NOIP C++14 竞赛标准的题解代码。

👨‍🏫 教练的解题分析

1. 核心思路：树上 DP (记忆化搜索)

这道题表面上是在问“燃烧”，实际上是在问：在一个隐式的有向图中，从哪个点出发能到达最多的节点。

• 隐式有向图：虽然输入是无向树，但火只能从高权值流向低权值。因此，对于树上相邻的两个点 $u, v$，如果 $a_u > a_v$，则存在一条 $u \to v$ 的有向边；如果 $a_u < a_v$，则存在 $v \to u$；如果相等，则断开。
• DAG 性质：由于权值严格单调递减，这个图一定不存在环（DAG）。
• 状态定义：设 $dp[u]$ 为点燃节点 $u$ 后，总共能燃烧的节点数量。
• 转移方程：$$dp[u] = 1 + \sum_{v \in \text{neighbors}(u), \ a_v < a_u} dp[v] $$即：$u$ 能烧到的点数 = 自己(1) + 所有比它小的邻居能烧到的点数之和。

2. 复杂度分析

• 朴素做法：如果对每个点都跑一遍完整的 DFS，对于一条长链（如 $N \to N-1 \to \dots \to 1$），时间复杂度会退化到 $O(N^2)$，对于 $N=10^5$ 的数据一定会超时（TLE）。
• 优化做法（记忆化）：我们在计算 $dp[u]$ 时，如果它的邻居 $v$ 的 $dp[v]$ 已经算过了，就直接拿来用，不要再递归下去。
  • 时间复杂度：$O(N)$。因为每个节点只会被真正计算一次，每条边最多被访问两次。
  • 空间复杂度：$O(N)$。用于存储邻接表、权值数组、DP 数组以及递归栈（最坏情况递归深度为 $N$）。

3. 优化建议

• 输入输出：数据量 $N=10^5$，建议使用关闭同步流的 cin/cout 或 scanf/printf。
• 栈空间：递归深度最大可达 $10^5$，在 NOIP/CSP 的 Linux 评测环境下（通常栈空间 8MB+）是安全的。

---

💻 标准题解代码 (C++14)

/**
 * P11378 [GESP202412 七级] 燃烧
 * 知识点：树上动态规划 (Tree DP)、记忆化搜索 (Memoization)
 * 
 * 时间复杂度：O(N) - 记忆化保证每个节点只计算一次
 * 空间复杂度：O(N) - 邻接表 + 递归栈 + DP数组
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义最大节点数，稍微开大一点防止边界溢出
const int MAXN = 100005;

// a[i]: 存储节点 i 的权值
int a[MAXN];

// dp[i]: 存储从节点 i 开始燃烧能覆盖的节点总数
// 初始化为 0，表示该状态尚未计算
int dp[MAXN];

// adj[i]: 邻接表，存储与节点 i 相连的所有节点
vector<int> adj[MAXN];

int n;

/**
 * 记忆化搜索函数
 * @param u 当前所在的节点
 * @return 从 u 开始能燃烧的节点总数
 */
int dfs(int u) {
    // 【关键点1】记忆化检查
    // 如果 dp[u] 已经被计算过（非0），直接返回结果，避免重复计算。
    // 这是将复杂度从 O(N^2) 降至 O(N) 的核心。
    if (dp[u] != 0) {
        return dp[u];
    }
    
    // 初始计数为 1（包含 u 自己）
    int sum = 1;
    
    // 遍历 u 的所有邻居
    for (int v : adj[u]) {
        // 【关键点2】传播条件
        // 只有当邻居 v 的权值 **严格小于** u 的权值时，火才能传过去。
        // 由于权值严格减小，这里不需要 visited 数组来防环（不会流回父亲）。
        if (a[v] < a[u]) {
            sum += dfs(v);
        }
    }
    
    // 记录结果并返回
    return dp[u] = sum;
}

void solve() {
    // 读入节点数
    if (!(cin >> n)) return;
    
    // 读入权值
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // 初始化 DP 数组和邻接表（针对多组数据的情况，虽然本题是单组）
    // 为了代码的通用性，显式清空是个好习惯
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
        dp[i] = 0;
    }
    
    // 读入边信息，构建无向图
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int max_nodes = 0;
    
    // 枚举每一个节点作为初始引燃点
    // 虽然有循环，但由于记忆化 dfs 的存在，总计算量依然是 O(N)
    for (int i = 1; i <= n; ++i) {
        max_nodes = max(max_nodes, dfs(i));
    }
    
    cout << max_nodes << endl;
}

int main() {
    // 【优化建议】关闭 IO 同步流，加速输入输出
    // 对于 10^5 规模的数据，这可以显著降低 IO 耗时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

---

🔍 易错点与代码细节注释

1. 关于 Visited 数组：

   • 通常图的遍历需要 visited 数组防止死循环。
   • 但本题中，转移条件是 a[v] < a[u]。假设是从父节点 p 走到 u，必然有 a[p] > a[u]。当我们检查 u 的邻居时，虽然包含 p，但判断 a[p] < a[u] 会失败。
   • 结论：由于权值单调递减，天然无环，不会走回头路，所以不需要额外的 visited 标记。

2. DP 数组的含义：

   • dp[u] 存的是“以 u 为根的符合条件的子树大小”。它一旦算出来，对于任何想流向 u 的上游节点来说，这个值都是固定的。

3. 栈溢出风险：

   • 在极端数据下（例如 $10^5$ 个点连成一条链，权值依次递减），递归深度会达到 $10^5$。
   • Windows 本地编译器默认栈较小（通常 1MB-2MB），运行这种数据可能会崩溃（Stack Overflow）。
   • 解决方案：不要惊慌。竞赛评测机（Linux 环境）通常提供 8MB 或更大的栈空间，足以支持 $10^5$ 层递归。如果在本地调试报错，可以尝试扩栈指令或改用手动模拟栈（但本题通常不需要）。

你好！我是你的OI金牌教练。这是一道非常经典的树上动态规划（Tree DP）或者说是记忆化搜索的题目。题目模型虽然简单，但考察了对图的遍历方向性和无环性的理解。

我们先放下代码，拿起草稿纸，一起来剖析这道题。

---

一、 核心关键词与题意解码

1. “树”：

   • 这意味着图是连通的，且没有环。任意两点间路径唯一。

2. “权值严格小于”：

   • 这是火势蔓延的唯一条件。$u$ 能点燃 $v$，当且仅当 $u$ 和 $v$ 相邻且 $a_v < a_u$。
   • 隐含意义：火势就像水往低处流一样，只能从高权值节点流向低权值节点。因为是“严格小于”，所以不可能流回去（不可能存在 $u \to v \to \dots \to u$ 的循环），也不可能在相等权值的节点间蔓延。
   • 这是一个隐含的 DAG（有向无环图） 结构。

3. “最多可以燃烧多少个节点”：

   • 我们需要枚举每一个节点作为起点，计算它能覆盖的节点数，取最大值。

---

二、 预备知识点

1. 图的存储：邻接表（vector<int> adj[]）。
2. 深度优先搜索（DFS）：用于遍历树。
3. 记忆化搜索（Memoization）：避免重复计算，是 DP 的一种实现方式。
   • 如果直接对每个点跑一遍 DFS，时间复杂度是 $O(N^2)$，对于 $N=10^5$ 会超时。我们需要 $O(N)$ 的解法。

---

三、 启发式教学：草稿纸上的推理演练

教练引导： 想象一下，这棵树是一个滑滑梯网络。每个节点的高度是它的权值 $a_i$。如果你在一个节点倒水，水会顺着管子流向所有比它低的邻居。

场景模拟： 假设有这样一条链：$5 - 2 - 3$。

• 起点选 5：5 比 2 高，水流向 2。2 比 3 低，水流不到 3。
  • 燃烧：5, 2。总数 2。
• 起点选 2：2 比 5 低，2 比 3 低。水哪里也流不去。
  • 燃烧：2。总数 1。
• 起点选 3：3 比 2 高，水流向 2。2 比 5 低，停。
  • 燃烧：3, 2。总数 2。

关键发现： 当我们计算“从 5 开始能烧多少”时，我们发现它烧到了 2。 如果我们以后计算其他节点（比如一个连接到 5 的点，权值为 10），当火烧到 5 时，5 能继续烧到的节点数是固定的，跟火是从哪里来的没关系。

• 为什么没关系？因为火是从“高”处来的（比如 10），而 5 只能往“低”处烧（比如 2）。由于 $10 > 5 > 2$，5 绝不可能烧回 10。

状态定义： 令 $dp[u]$ 表示如果点燃节点 $u$，以 $u$ 为根，水流自然向下能覆盖的节点总数。

转移方程：

$$dp[u] = 1 + \sum_{v \in \text{neighbors}(u), \ a_v < a_u} dp[v] $$

• 这个 $1$ 是 $u$ 自己。
• 求和部分是所有比 $u$ 小的邻居 $v$ 能贡献的数量。

复杂度分析： 有了记忆化（算过 $dp[u]$ 就存下来，下次直接用），每个节点只会被计算一次。 总时间复杂度从 $O(N^2)$ 降为 $O(N)$。

---

四、 题解标准代码 (C++14)

/**
 * P11378 [GESP202412 七级] 燃烧
 * 知识点：树上DP、记忆化搜索
 * 
 * 复杂度分析：
 * 时间复杂度：O(N)。每个节点只会被 dfs 计算一次，每条边最多被访问两次（双向各判断一次）。
 * 空间复杂度：O(N)。用于存储邻接表、权值数组和 DP 数组，以及递归栈的空间。
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

// 存储节点权值
int a[MAXN];
// 邻接表存图
vector<int> adj[MAXN];
// dp[u] 记录从 u 开始能燃烧的节点数量（记忆化数组）
// 初始化为 0，表示未计算
int dp[MAXN];
int n;

// 记忆化搜索函数
int dfs(int u) {
    // 如果已经计算过，直接返回结果
    if (dp[u] != 0) {
        return dp[u];
    }
    
    // 初始燃烧数量为 1（节点 u 自身）
    int sum = 1;
    
    // 遍历 u 的所有邻居
    for (int v : adj[u]) {
        // 核心逻辑：只有当邻居 v 的权值严格小于 u 时，火才能传过去
        if (a[v] < a[u]) {
            // 累加邻居能燃烧的节点数
            sum += dfs(v);
        }
    }
    
    // 记录结果并返回
    return dp[u] = sum;
}

int main() {
    // 优化 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n)) return 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int max_burn = 0;
    // 枚举每一个点作为初始引燃点
    for (int i = 1; i <= n; ++i) {
        max_burn = max(max_burn, dfs(i));
    }
    
    cout << max_burn << endl;
    
    return 0;
}

五、 关键点与易错点注释

1. 记忆化是核心：
   • 代码中的 if (dp[u] != 0) return dp[u]; 是将复杂度降到线性的关键。没有这句会超时。
2. 不需要 visited 数组或 parent 参数：
   • 通常树的 DFS 需要防止走回头路（走回父亲）。
   • 但在这里，传播条件是 $a_v < a_u$。假设是从父亲 $p$ 传给 $u$ 的，必然有 $a_p > a_u$。
   • 在计算 $u$ 的邻居时，检查到 $p$，判断条件是 $a_p < a_u$。由于 $a_p > a_u$，这个条件一定为假。
   • 所以火天然不会倒流，不需要额外的防止回溯逻辑。
3. 栈溢出风险：
   • 对于 $N=10^5$ 的链状数据，递归深度可能达到 $10^5$。在部分栈空间较小的环境（如 Windows 本地默认栈，或某些限制严格的 OJ）可能会爆栈。
   • 优化建议：C++ 在大多数现代 OJ（Linux环境）通常给 8MB 以上栈空间，足够 $10^5$ 深度。如果遇到 Stack Overflow，可以改用拓扑排序或手动模拟栈，但本题标准解法通常认可递归。

---

六、 数据生成器 (Data Generator)

这是一份用于生成测试数据的代码，涵盖了链状、菊花图、随机树等情况，并对权值做了特殊构造以覆盖边界。

/**
 * P11378 数据生成器
 * 生成 1.in ~ 10.in 及对应的 .out
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
#include <random>
#include <ctime>
#include <numeric>

using namespace std;

// ================== Solver (标准解法) ==================
const int MAXN_S = 100005;
int a_s[MAXN_S];
vector<int> adj_s[MAXN_S];
int dp_s[MAXN_S];

int dfs_s(int u) {
    if (dp_s[u] != 0) return dp_s[u];
    int sum = 1;
    for (int v : adj_s[u]) {
        if (a_s[v] < a_s[u]) {
            sum += dfs_s(v);
        }
    }
    return dp_s[u] = sum;
}

int solve(int n, const vector<int>& vals, const vector<pair<int, int>>& edges) {
    // Reset
    for(int i=1; i<=n; ++i) {
        adj_s[i].clear();
        dp_s[i] = 0;
        a_s[i] = vals[i-1];
    }
    for(auto& e : edges) {
        adj_s[e.first].push_back(e.second);
        adj_s[e.second].push_back(e.first);
    }
    int ans = 0;
    for(int i=1; i<=n; ++i) ans = max(ans, dfs_s(i));
    return ans;
}

// ================== Generator ==================
mt19937 rng(time(0));

int rand_int(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

void generate_case(int id) {
    int n;
    // 根据子任务设置 N 的大小
    if (id <= 2) n = rand_int(5, 10);          // Subtask 1: N <= 10
    else if (id <= 4) n = rand_int(50, 100);   // Subtask 2: N <= 100
    else if (id <= 9) n = rand_int(50000, 100000); // Subtask 3: N <= 10^5
    else n = 100000; // Limit case

    vector<int> vals(n);
    vector<pair<int, int>> edges;

    // 构造权值策略
    if (id == 5) { 
        // 所有权值相同 -> 答案应为 1
        int v = rand_int(1, 1000);
        for(int i=0; i<n; ++i) vals[i] = v;
    } else if (id == 6) {
        // 权值严格递增 (1, 2, 3...)
        iota(vals.begin(), vals.end(), 1);
    } else {
        // 随机权值
        for(int i=0; i<n; ++i) vals[i] = rand_int(1, 1000000);
    }

    // 构造树结构策略
    if (id == 7) { 
        // 链状结构 (Line)
        for(int i=2; i<=n; ++i) edges.push_back({i-1, i});
        // 配合权值打乱，测试深度
        if (id == 6) { /* 保持有序链 */ } 
        else shuffle(vals.begin(), vals.end(), rng);
    } else if (id == 8) {
        // 菊花图 (Star)
        for(int i=2; i<=n; ++i) edges.push_back({1, i});
    } else {
        // 随机树 (Random Parent)
        // 节点 i 连接到 [1, i-1] 中的一个
        for(int i=2; i<=n; ++i) {
            int p = rand_int(1, i-1);
            edges.push_back({p, i});
        }
    }

    // 输出 .in
    string in_name = to_string(id) + ".in";
    ofstream fin(in_name);
    fin << n << "\n";
    for(int i=0; i<n; ++i) fin << vals[i] << (i==n-1?"":" ");
    fin << "\n";
    
    // 随机打乱边的顺序和端点方向，避免数据生成器的偏好被利用
    shuffle(edges.begin(), edges.end(), rng);
    for(auto& e : edges) {
        if (rand_int(0, 1)) fin << e.first << " " << e.second << "\n";
        else fin << e.second << " " << e.first << "\n";
    }
    fin.close();

    // 输出 .out
    string out_name = to_string(id) + ".out";
    ofstream fout(out_name);
    fout << solve(n, vals, edges) << "\n";
    fout.close();
    
    cout << "Generated Case " << id << " (N=" << n << ")" << endl;
}

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