题目解析

本题要求计算树中每个节点的威胁值。威胁值定义为：从该节点出发，沿着到根节点的路径向上走，所有可能垂直路径的交替和的最大值。

交替和的计算规则：路径上的节点按从当前节点到根节点的顺序，符号交替变化（第一个节点取正，第二个取负，第三个取正，依此类推）。

---

核心思想

1. 符号规律

对于从节点 $v$ 到根节点的路径，设路径上的节点序列为 $[v, p_v, p_{p_v}, \dots, 1]$，则：

• 第 $1$ 个节点（$v$ 自身）符号为 $+$
• 第 $2$ 个节点（父节点）符号为 $-$
• 第 $3$ 个节点符号为 $+$
• 第 $4$ 个节点符号为 $-$
• 依此类推...

2. 动态规划状态定义

设：

• $f(v)$：从节点 $v$ 出发的所有垂直路径中，交替和的最大值（这就是答案）
• $g(v)$：从节点 $v$ 出发的所有垂直路径中，交替和的最小值

3. 递推关系推导

考虑节点 $v$ 和它的父节点 $p$：

计算 $f(v)$

从节点 $v$ 出发的垂直路径有两种情况：

1. 路径只包含 $v$ 自身：交替和 $= a_v$

2. 路径包含 $v$ 和它的若干祖先：设从父节点 $p$ 出发的某条路径的交替和为 $S$，则从 $v$ 出发包含该路径的交替和为 $a_v - S$

为了最大化 $a_v - S$，需要 $S$ 尽可能小。因此： $f(v) = \max(a_v,\ a_v - g(p))$

计算 $g(v)$

同理，从节点 $v$ 出发的最小交替和也有两种情况：

1. 路径只包含 $v$ 自身：$a_v$

2. 路径包含 $v$ 和祖先：$a_v - S$，此时需要 $S$ 尽可能大才能让结果最小，所以： $g(v) = \min(a_v,\ a_v - f(p))$

4. 边界条件（根节点）

根节点 $1$ 没有父节点，它的路径只能是它自身： $f(1) = a_1,\quad g(1) = a_1$

---

代码实现

递归函数设计

void solve(int v, int p, long long mini, long long maxi)

参数含义：

• v：当前节点
• p：父节点
• mini：父节点的 $g(p)$ 值（父节点的最小交替和）
• maxi：父节点的 $f(p)$ 值（父节点的最大交替和）

步骤详解

// 1. 计算当前节点的答案 f(v)
res[v] = max(arr[v], mini * -1 + arr[v]);
// 即：max(a_v, a_v - g(p))

// 2. 计算当前节点的最小交替和 g(v)
mini = min(arr[v], maxi * -1 + arr[v]);
// 即：min(a_v, a_v - f(p))

// 3. 递归处理子节点
for (int u : gr[v]) {
    if (u == p) continue;
    solve(u, v, mini, res[v]);
}
// 将当前节点的 g(v) 和 f(v) 传递给子节点

初始化

根节点从 solve(0, -1, 0, 0) 开始：

• mini = 0，maxi = 0

对于根节点：

res[0] = max(arr[0], 0 * -1 + arr[0]) = max(arr[0], arr[0]) = arr[0];
mini = min(arr[0], 0 * -1 + arr[0]) = min(arr[0], arr[0]) = arr[0];

所以根节点的 $f(1)=a_1$，$g(1)=a_1$，符合边界条件。

---

验证：

考虑第一个测试用例：

• $n = 5$
• $a = [4, 5, 2, 6, 7]$
• 边：$1-2,\ 3-2,\ 4-3,\ 5-1$（节点编号从 $1$ 开始，代码中转换为 $0$ 索引）

计算过程

根节点 $1$（索引 $0$）：

• $f(0) = 4$
• $g(0) = 4$

节点 $2$（索引 $1$，父节点 $0$）：

• $f(1) = \max(5,\ 5 - g(0)) = \max(5,\ 5-4) = \max(5,1) = 5$
• $g(1) = \min(5,\ 5 - f(0)) = \min(5,\ 5-4) = \min(5,1) = 1$

节点 $3$（索引 $2$，父节点 $1$）：

• $f(2) = \max(2,\ 2 - g(1)) = \max(2,\ 2-1) = \max(2,1) = 2$
• $g(2) = \min(2,\ 2 - f(1)) = \min(2,\ 2-5) = \min(2,-3) = -3$

节点 $4$（索引 $3$，父节点 $2$）：

• $f(3) = \max(6,\ 6 - g(2)) = \max(6,\ 6-(-3)) = \max(6,9) = 9$
• $g(3) = \min(6,\ 6 - f(2)) = \min(6,\ 6-2) = \min(6,4) = 4$

节点 $5$（索引 $4$，父节点 $0$）：

• $f(4) = \max(7,\ 7 - g(0)) = \max(7,\ 7-4) = \max(7,3) = 7$
• $g(4) = \min(7,\ 7 - f(0)) = \min(7,\ 7-4) = \min(7,3) = 3$

最终 $f$ 值：$[4, 5, 2, 9, 7]$，与样例输出一致。

---

复杂度分析

• 时间复杂度：$O(n)$，每个节点只访问一次
• 空间复杂度：$O(n)$，存储树的邻接表和结果数组

由于所有测试用例的 $n$ 之和不超过 $2 \times 10^5$，完全可行。

---

总结

递推式	含义
$f(v) = \max(a_v,\ a_v - g(p))$	节点 $v$ 的最大交替和（答案）
$g(v) = \min(a_v,\ a_v - f(p))$	节点 $v$ 的最小交替和
边界条件	$f(1) = g(1) = a_1$

核心思想：

1. 通过 DFS 遍历树，利用父节点已计算的值更新子节点
2. 维护两个值：最大交替和 $f(v)$ 和最小交替和 $g(v)$
3. 子节点的 $f$ 依赖父节点的 $g$，子节点的 $g$ 依赖父节点的 $f$

一次 DFS 即可解决！