你好！我是你的OI金牌教练。

考虑到 $N=10^5$ 的数据范围，递归 DFS 在极端情况下（如链状树）会发生栈溢出 (Stack Overflow)。 为了提供最严谨、最鲁棒的教学内容，我对题目、解析及代码进行了修正和优化。特别是将标准解法改为了 非递归（防爆栈） 写法。

---

第一部分：背景知识讲解

1. 汉武帝与推恩令 (The Order of Expanding Favors)

西汉初期，诸侯王势力过大，威胁中央。汉武帝采纳主父偃的建议，颁布“推恩令”。规定诸侯王死后，除嫡长子继承王位外，其他子弟也可分割王国土地为列侯，由郡守统辖。此举兵不血刃地削弱了诸侯势力。

2. 算法模型：树形 DP (最大权独立集)

在这个宗室关系树中，存在父子层级。 为了防止结党营私，汉武帝选拔人才时规定：父子不能同时入选。 每个节点都有一个权值，我们需要在满足“父子不同时入选”的前提下，选出若干节点，使得权值之和最大。 这在算法竞赛中被称为 “没有上司的舞会” 或 树上最大权独立集问题。

---

第二部分：题目内容

题目名称：推恩令的赏赐 (The Reward of Tui En Ling)

题目描述

汉武帝刘彻在颁布推恩令后，决定对刘氏宗亲进行赏赐。 宗室关系构成了一棵树，共有 $N$ 名宗亲，编号为 $1$ 到 $N$。其中 $1$ 号是宗正（根节点）。除了 $1$ 号，每个人都有且仅有一位直接父亲。

每位宗亲都有一个**“能力值”** $V_i$（可能为负，表示有过错）。 汉武帝计划从中挑选一部分宗亲授予“金印”，选拔规则如下： 如果某位宗亲被选中，那么他的直接父亲和直接儿子都不能被选中。（即树上相邻的两个节点不能同时被选）。

请你编写程序，计算出在符合规则的前提下，被选中的宗亲能力值之和的最大值。

输入格式

第一行包含一个正整数 $N$，表示宗亲的数量。

第二行包含 $N$ 个整数 $V_1, V_2, \dots, V_N$，表示每位宗亲的能力值。

接下来 $N-1$ 行，每行包含两个正整数 $u, v$，表示 $u$ 是 $v$ 的父亲。

输出格式

输出一行一个整数，表示能获得的最大能力值之和。

输入输出样例 #1

输入：

7
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7

输出：

5

样例 #1 解释： 树结构：

      1
     / \
    2   3
   / \ / \
  4  5 6  7

• 方案：选择 {1, 4, 5, 6, 7}。
• 验证：
  • 1选了，2、3没选（合法）。
  • 2没选，4、5选了（合法）。
  • 3没选，6、7选了（合法）。
• 总分：$1+1+1+1+1 = 5$。

输入输出样例 #2

输入：

5
10 -5 10 8 -2
1 2
1 3
2 4
2 5

输出：

18

样例 #2 解释： 树结构：

      1(10)
     /    \
  2(-5)   3(10)
  /   \
4(8)  5(-2)

• DP 推导：
  • 节点4：选=8，不选=0。
  • 节点5：选=-2，不选=0。
  • 节点3：选=10，不选=0。
  • 节点2：
    • 选（得-5）：子节点4、5不能选 -> $-5 + 0 + 0 = -5$。
    • 不选：子节点4、5可选可不选 -> $\max(8,0) + \max(-2,0) = 8$。
  • 节点1：
    • 选（得10）：子节点2、3不能选(即取不选2、不选3的值) -> $10 + 8 + 0 = 18$。
    • 不选：子节点2、3可选可不选 -> $\max(-5, 8) + \max(10, 0) = 8 + 10 = 18$。
• 最大值为 18。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $-1000 \le V_i \le 1000$
• 保证是一棵树，根节点为 1。

---

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

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 防爆栈版)

见题解