这里提供一份完整的数据生成器代码（generator.cpp）。编译并运行此代码后，它会在当前目录下自动生成 10 组测试数据（1.in/1.out 到 10.in/10.out），涵盖了题目要求的各类情况。

数据生成器功能说明：

1. 覆盖范围：
   • Test 1-3：小规模数据（$N \le 50$），包含随机树、链状、星状结构，便于手动验证。
   • Test 4-5：边界值测试（全正数、全负数）。
   • Test 6：中等规模随机数据（$N=1000$，覆盖 60% 数据点）。
   • Test 7-10：大规模数据（$N=16000$，覆盖 100% 数据点），包含深链、大星、大随机树。
2. 解题逻辑：内置了标准的树形 DP + 贪心算法（AC代码），确保生成的 .out 文件绝对正确。
3. 随机性：使用 mt19937 高质量随机数引擎，防止生成的数据过于单一。

生成器代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <climits>
#include <chrono>

using namespace std;

// ==========================================
// 第一部分：标准解题逻辑 (用于生成 .out)
// ==========================================

const int MAXN = 16005;
int w[MAXN];
int dp[MAXN];
vector<int> adj[MAXN];
int ans = INT_MIN;

// 标准树形DP求解函数
void dfs_solve(int u, int fa) {
    dp[u] = w[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs_solve(v, u);
        // 贪心：如果子树收益为正，则保留
        if (dp[v] > 0) {
            dp[u] += dp[v];
        }
    }
    ans = max(ans, dp[u]);
}

int solve_case(int n, const vector<int>& weights, const vector<pair<int, int>>& edges) {
    // 1. 清空全局状态
    ans = INT_MIN;
    for (int i = 0; i <= n; i++) {
        adj[i].clear();
        dp[i] = 0;
        w[i] = 0;
    }

    // 2. 载入数据
    for (int i = 1; i <= n; i++) {
        w[i] = weights[i - 1]; // weights 0-based转为 w 1-based
    }
    for (const auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    // 3. 求解
    dfs_solve(1, 0);
    return ans;
}

// ==========================================
// 第二部分：数据生成工具
// ==========================================

// 初始化随机数引擎
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

// 生成单个测试点
// type: "random", "chain" (链状), "star" (星状)
// weight_type: "mixed" (混合), "positive" (全正), "negative" (全负)
void generate_data(int case_id, int n, string type, string weight_type) {
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    ofstream fout(in_file);
    fout << n << endl;

    // 1. 生成权值
    vector<int> weights;
    for (int i = 0; i < n; i++) {
        int val;
        if (weight_type == "positive") {
            val = random_int(1, 10000); // 纯正数
        } else if (weight_type == "negative") {
            val = random_int(-10000, -1); // 纯负数
        } else {
            // 混合：大概率生成绝对值较大的数，增加贪心难度
            val = random_int(-10000, 10000);
        }
        weights.push_back(val);
        fout << val << (i == n - 1 ? "" : " ");
    }
    fout << endl;

    // 2. 生成树结构 (边)
    vector<pair<int, int>> edges;
    if (type == "chain") {
        // 链状树: 1-2-3-4...
        // 这种结构测试递归深度和线性传递
        vector<int> p(n);
        for(int i=0; i<n; i++) p[i] = i+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连所有
        // 测试聚合能力
        for (int i = 2; i <= n; i++) {
            edges.push_back({1, i});
        }
    } else {
        // 随机树: 每个点 i 随机连向 1...(i-1) 中的一个点
        // 这是生成连通树的标准简易方法
        for (int i = 2; i <= n; i++) {
            int parent = random_int(1, i - 1);
            edges.push_back({parent, i});
        }
    }

    // 打乱边的输出顺序
    shuffle(edges.begin(), edges.end(), rng);

    // 输出边
    for (const auto& e : edges) {
        fout << e.first << " " << e.second << endl;
    }
    fout.close();

    // 3. 计算标准答案并输出
    int result = solve_case(n, weights, edges);
    ofstream f_ans(out_file);
    f_ans << result << endl;
    f_ans.close();

    cout << "Generated Case " << case_id << ": N=" << n 
         << " [" << type << "/" << weight_type << "] -> Ans=" << result << endl;
}

int main() {
    // 题目限制: N <= 16000
    
    // Test 1: 小数据，随机
    generate_data(1, 10, "random", "mixed");

    // Test 2: 小数据，链状
    generate_data(2, 20, "chain", "mixed");

    // Test 3: 小数据，星状
    generate_data(3, 20, "star", "mixed");

    // Test 4: 边界 - 全正数 (N=100)，答案应为所有数之和
    generate_data(4, 100, "random", "positive");

    // Test 5: 边界 - 全负数 (N=100)，答案应为最大的那个负数
    generate_data(5, 100, "random", "negative");

    // Test 6: 中等数据 (N=1000)，对应 60% 数据点
    generate_data(6, 1000, "random", "mixed");

    // Test 7: 大数据 (N=16000)，链状，混合权值
    generate_data(7, 16000, "chain", "mixed");

    // Test 8: 大数据 (N=16000)，星状，混合权值
    generate_data(8, 16000, "star", "mixed");

    // Test 9: 大数据 (N=16000)，随机树，混合权值
    generate_data(9, 16000, "random", "mixed");

    // Test 10: 极限数据，随机树
    generate_data(10, 16000, "random", "mixed");

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

如何使用：

1. 将上述代码保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o generator -std=c++11。
3. 运行程序：./generator（Windows 下是 generator.exe）。
4. 程序运行结束后，你的文件夹里会出现 1.in, 1.out ... 10.in, 10.out。
5. 将这些文件打包上传到你的 OJ 后台即可。

你好！我是你的OI教练。

这道 P1122《最大子树和》是一道非常经典的树形 DP 入门题，同时也是考察贪心思想的好题。

相比前两道题，这道题的代码量更少，但核心在于理解：为什么碰到负贡献的子树要果断舍弃。

下面是符合 NOIP C++14 标准的 AC 代码。

核心代码 (C++14 NOIP标准)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // 用于使用 INT_MIN

using namespace std;

// 数据规模 N <= 16000
const int MAXN = 16005;

// w[i]: 第 i 朵花的美丽指数
int w[MAXN];

// dp[u]: 以 u 为根，且【必须包含 u 本身】的子树最大权值和
// 为什么要包含 u？因为如果不包含 u，u 的子节点就无法和 u 的父节点连通了
int dp[MAXN];

// 邻接表存图
vector<int> adj[MAXN];

// 全局答案，初始化为极小值
// 易错点：不要初始化为 0！如果所有花都是负数，答案应该是那个最大的负数，而不是 0
int ans = INT_MIN;

void dfs(int u, int fa) {
    // 1. 初始化当前节点的 DP 值
    // 基础情况：只选自己
    dp[u] = w[u];

    // 2. 遍历所有子节点
    for (int v : adj[u]) {
        if (v == fa) continue; // 防止走回头路（这是无向图）

        dfs(v, u); // 递归先算儿子

        // 3. 贪心决策 / 状态转移
        // 如果子树 v 的最大贡献是正数，那就连上它（赚钱就带着玩）
        // 如果子树 v 的最大贡献是负数，那就剪断（亏钱就不带它玩），相当于 + 0
        if (dp[v] > 0) {
            dp[u] += dp[v];
        }
    }

    // 4. 更新全局最优解
    // 注意：最大子树和不一定非要包含整棵树的根节点（比如树根是负无穷）
    // 所以我们在 DFS 过程中，记录出现过的最大 dp 值
    ans = max(ans, dp[u]);
}

int main() {
    // 竞赛标准 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    // 读入美丽指数
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    // 读入边（无向图）
    // 题目输入 n-1 行，标准的树结构
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 树形 DP 入口
    // 题目给的是无向连通图（树），随便选一个点做根即可，通常选 1
    dfs(1, 0);

    cout << ans << endl;

    return 0;
}

👨‍🏫 教练划重点（关键点与易错点）

1. 全局变量 ans 的初始化：

   • 易错等级：⭐⭐⭐⭐⭐
   • 错误做法：int ans = 0;
   • 原因：如果输入的数据全是负数（例如 -5 -2 -9），题目要求修剪后至少剩下一朵花。正确的答案应该是 -2。如果初始化为 0，就会 WA。
   • 正确做法：初始化为 INT_MIN 或者 w[1]（读入第一个数后赋值）。

2. 状态定义的连通性：

   • 我们定义 $dp[u]$ 时，强调必须包含 $u$。
   • 如果不强制包含 $u$，那么 $dp[u]$ 可能会取到 $u$ 下面某个断开的子树的值，这样 $u$ 在向上回溯给它父亲汇报时，父亲连上的就不是 $u$ 所在的连通块了，链条就断了。

3. 无向图的处理：

   • 题目给的是边，没有父子关系。
   • 存图用 push_back 两次。
   • DFS 时必须带上 fa 参数，并且 if (v == fa) continue;，否则会死循环（父调子，子调父）。

4. 最终答案的位置：

   • 易错等级：⭐⭐⭐
   • 不要直接输出 dp[1]。
   • 虽然我们在做 DFS，但最优解的那个“最大子树”可能是在树的深处，跟根节点 1 毫无关系（比如根节点是 -10000）。所以在 DFS 过程中要时刻维护 ans。

这道题代码非常简洁，是理解树形 DP + 贪心思想的绝佳例题。一定要自己手敲一遍哦！

你好！我是你的OI教练。

恭喜你来到了树形DP的第三站——P1122《最大子树和》。 如果说前两题（没有上司的舞会、战略游戏）是在教你怎么处理“父子约束关系”，那么这道题就是在教你树上的贪心决策。

这道题其实比前两题更直观，状态也更简单（不需要二维数组）。来，拿出草稿纸，我们开始分析。

第一部分：思路提示

1. 题目翻译（抓重点）

• “修剪枝条” = 断开边。
• “扔掉一株” = 只保留一部分连通的节点。
• “剩下的花卉” = 选出一个连通子图。
• 目标：让选出来的这个连通子图的点权之和最大。

2. 贪心的直觉 想象你是一个带头大哥（节点 $u$），你的手下（子节点 $v$）想带着他的小团队加入你的帮派。

• 如果手下 $v$ 的团队总资产是正数（能帮你赚钱），你要不要他？肯定要！
• 如果手下 $v$ 的团队总资产是负数（会拉低你的总资产），你要不要他？肯定踢掉（剪断枝条）！

3. 为什么需要 DP？ 因为你不能光看手下 $v$ 一个人的数值，你要看 $v$ 这一整支分支如果不被剪断，能贡献多少最大价值。 这就构成了递归子问题：父亲的值依赖于儿子的最大贡献值。

4. 谁是根？ 题目给的是无向图，没有指定根。 但对于“连通块”问题，选谁做根都不影响结果。为了方便写代码，我们通常默认 1号节点 是整棵树的根，把无根树变成有根树处理。

第二部分：预备知识点总结

1. DFS（后序遍历）：必须先算出子树的结果，才能算父亲，所以是自底向上的过程。
2. 树形 DP 的基本状态：
   • $dp[u]$：表示以 $u$ 为根（且必须包含 $u$ 自己）的子树中，能选出的最大权值和。
   • 注意：必须包含 $u$ 是为了保证连通性。如果 $u$ 都不选，那 $u$ 的儿子们就和 $u$ 的父亲断开了。
3. 贪心算法：$\max(val, 0)$ 的思想。
4. 全局最优解：答案不一定是 $dp[root]$，因为最大和的连通块可能只在树的某个角落，不一定包含根节点。

第三部分：启发式教学 —— 草稿纸上的推演

来，画一棵简单的树，我们要填满 dp 表。

场景图示： 每个圈里的数字是它的美丽指数（权值）。

       1 (权值: -2)
      /    \
     /      \
    2 (权:5) 3 (权:-10)
    |
    |
    4 (权:8)

我们定义 $dp[u]$：以 $u$ 为根，且必须保留 $u$ 的最大连通块权值。

开始 DFS 遍历（后序）：

第一步：看叶子节点 4

• 它没有子节点。
• 必须保留自己：$dp[4] = 8$。
• 草稿纸记录：dp[4]=8

第二步：看节点 3

• 它没有子节点。
• 必须保留自己：$dp[3] = -10$。
• 草稿纸记录：dp[3]=-10

第三步：看节点 2（它有一个儿子 4）

• 先拿上自己的：$dp[2] = 5$。
• 决策时刻：儿子 4 的 $dp[4]$ 是 $8$。
  • $8 > 0$，是正资产！
  • 连接 4 号节点划算吗？划算！
  • $dp[2] = 5 + 8 = 13$。
• 草稿纸记录：dp[2]=13

第四步：看根节点 1（它有儿子 2 和 3）

• 先拿上自己的：$dp[1] = -2$。
• 决策时刻 A：看儿子 2。
  • $dp[2] = 13$。是正数，要了！
  • $dp[1] += 13 \rightarrow 11$。
• 决策时刻 B：看儿子 3。
  • $dp[3] = -10$。是负数，那是债务，剪掉！
  • 不要儿子 3。$dp[1]$ 保持 11。
• 草稿纸记录：dp[1]=11

第五步：找全局最大值 回头看一眼所有的 $dp$ 值：

• $dp[4] = 8$
• $dp[3] = -10$
• $dp[2] = 13$
• $dp[1] = 11$

答案是 13。 （对应的连通块是：节点 2 和节点 4 组成的小团体，不带节点 1 玩，也不带节点 3 玩）。

代码逻辑框架（填空题）：

vector<int> adj[N];
int w[N]; // 美丽指数
int dp[N];
int ans = -2147483647; // 初始化为极小值

void dfs(int u, int fa) {
    dp[u] = w[u]; // 先加上自己的权值
    
    for (int v : adj[u]) {
        if (v == fa) continue; // 别倒着搜回父亲去了
        
        dfs(v, u); // 递归算儿子
        
        // 贪心决策：如果儿子贡献是正的，就加上
        if (dp[v] > 0) {
            dp[u] += dp[v];
        }
    }
    
    // 每次算完一个点，都要尝试更新全局答案
    // 因为最大连通块不一定包含根节点
    ans = max(ans, dp[u]);
}

int main() {
    // 1. 读入 n
    // 2. 读入权值 w[i]
    // 3. 读入边，建无向图
    // 4. dfs(1, 0)
    // 5. 输出 ans
}

这道题其实是树形DP里最“爽”的一道，因为逻辑非常符合直觉。快去试试吧！