第三部分：题目分析与标准代码

1. 核心思想：树形 DP

我们需要对每个节点 $u$ 维护两个状态：

• dp[u][0]：不选 $u$，以 $u$ 为根的子树的最大权值和。
• dp[u][1]：选 $u$，以 $u$ 为根的子树的最大权值和。

状态转移方程：

$$\begin{cases} dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1]) \\ dp[u][1] = V_u + \sum_{v \in children(u)} dp[v][0] \end{cases} $$

2. 工程化优化：非递归实现

虽然递归 DFS 写法简单，但在 $N=10^5$ 且树退化为链时，会导致栈溢出。 我们采用 BFS 求拓扑序 + 逆序遍历 的方法：

1. BFS：从根开始广度优先搜索，记录访问节点的顺序（层序）。这样保证了父亲一定在儿子前面。
2. 逆序遍历：从 BFS 序列的最后（叶子节点）向前遍历到根。处理节点 $u$ 时，其所有子节点 $v$ 必定已经处理完毕，可以直接利用子节点的状态更新父节点。

3. 标准代码 (C++14 防爆栈版)

/**
 * 题目：推恩令的赏赐
 * 难度：GESP 6级 / 提高-
 * 算法：树形 DP (非递归优化版)
 * 时间复杂度：O(N)
 */

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

using namespace std;

// IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 邻接表
vector<int> adj[MAXN];
// 权值
int val[MAXN];
// 父节点记录（用于逆序更新）
int parent[MAXN];
// dp[u][0] 不选u, dp[u][1] 选u
long long dp[MAXN][2];

void solve() {
    int N;
    if (!(cin >> N)) return;

    // 清空（多测时需要，单测可选）
    for(int i=1; i<=N; i++) {
        adj[i].clear();
        parent[i] = 0;
    }

    for (int i = 1; i <= N; ++i) {
        cin >> val[i];
    }

    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        // 记录 v 的父亲是 u，用于后续 DP 更新
        parent[v] = u; 
    }

    // 1. BFS 获取拓扑序 (层序)
    vector<int> order;
    order.reserve(N);
    queue<int> q;
    
    q.push(1); // 根节点入队

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : adj[u]) {
            q.push(v);
        }
    }

    // 2. 逆序遍历 (从叶子到根)
    for (int i = N - 1; i >= 0; --i) {
        int u = order[i];
        
        // 初始化当前节点状态
        dp[u][0] = 0;
        dp[u][1] = val[u];

        // 遍历 u 的所有子节点 v
        for (int v : adj[u]) {
            // 状态转移
            dp[u][0] += max(dp[v][0], dp[v][1]); // u不选，v可选可不选
            dp[u][1] += dp[v][0];                // u选，v必不能选
        }
    }

    // 3. 输出根节点的最优解
    cout << max(dp[1][0], dp[1][1]) << endl;
}

int main() {
    fast_io();
    solve();
    return 0;
}

---

第四部分：数据生成器

这是一个稳健的数据生成器，涵盖了链状、菊花图、随机树等各种形态，并且使用了非递归的标准解法来生成 .out 文件，确保生成过程不会崩溃。

/**
 * GESP 6级 [推恩令的赏赐] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out) - 防爆栈版
// ------------------------------------------
const int MAXN = 100005;
vector<int> g_adj[MAXN];
int g_val[MAXN];
long long g_dp[MAXN][2];

long long solve_std(int N, const vector<int>& vals, const vector<pair<int, int>>& edges) {
    // 初始化
    for(int i=1; i<=N; i++) g_adj[i].clear();
    for(int i=1; i<=N; i++) g_val[i] = vals[i-1];
    
    for(const auto& e : edges) {
        g_adj[e.first].push_back(e.second);
    }

    // BFS 序
    vector<int> order;
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for(int v : g_adj[u]) q.push(v);
    }

    // 逆序 DP
    for(int i = N-1; i >= 0; i--) {
        int u = order[i];
        g_dp[u][0] = 0;
        g_dp[u][1] = g_val[u];
        for(int v : g_adj[u]) {
            g_dp[u][0] += max(g_dp[v][0], g_dp[v][1]);
            g_dp[u][1] += g_dp[v][0];
        }
    }

    return max(g_dp[1][0], g_dp[1][1]);
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<int> vals;
        vector<pair<int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 7;
            vals = {1, 1, 1, 1, 1, 1, 1};
            edges = {{1,2}, {1,3}, {2,4}, {2,5}, {3,6}, {3,7}};
        }
        else if (i == 2) {
            // 样例2
            N = 5;
            vals = {10, -5, 10, 8, -2};
            edges = {{1,2}, {1,3}, {2,4}, {2,5}};
        }
        else if (i == 3) {
            // 链状，全正 (间隔选)
            N = 20;
            for(int k=0; k<N; k++) vals.push_back(10);
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
        }
        else if (i == 4) {
            // 链状，负数 (只选正的孤立点)
            N = 20;
            for(int k=0; k<N; k++) vals.push_back(randRange(-10, 10));
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
        }
        else if (i == 5) {
            // 菊花图 (1连所有)
            N = 100;
            vals.push_back(1000); // 根很大
            for(int k=1; k<N; k++) vals.push_back(10); // 叶子小
            for(int k=2; k<=N; k++) edges.push_back({1, k});
        }
        else if (i == 6) {
            // 菊花图 (根负数，叶子正数)
            N = 100;
            vals.push_back(-100);
            for(int k=1; k<N; k++) vals.push_back(10);
            for(int k=2; k<=N; k++) edges.push_back({1, k});
        }
        else if (i == 7) {
            // 大规模链状 (Stack Overflow Test)
            N = 100000;
            for(int k=0; k<N; k++) vals.push_back(randRange(1, 100));
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000;
            for(int k=0; k<N; k++) vals.push_back(randRange(-100, 1000));
            
            // 随机树生成：i 的父亲在 1~i-1 中随机
            // 这样保证 1 是根
            for(int k=2; k<=N; k++) {
                int p;
                if(i == 8) p = max(1, k-5); // 深树
                else p = randRange(max(1, k-1000), k-1); // 随机树
                edges.push_back({p, k});
            }
        }

        // 写入输入 (使用 \n 优化 I/O)
        fin << N << "\n";
        for (int k=0; k<N; k++) fin << vals[k] << (k==N-1?"":" ");
        fin << "\n";
        
        // 打乱边输出顺序
        random_shuffle(edges.begin(), edges.end());
        for (const auto& e : edges) {
            fin << e.first << " " << e.second << "\n";
        }

        // 写入输出
        fout << solve_std(N, vals, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}