题解

我们按深度分层处理。设 $d$ 为叶子深度，节点 $i$ 的深度为 $\text{depth}[i]$（根深度 $0$）。
定义 $dp[i]$ 表示：经过 $\text{depth}[i]$ 次移动后（即第 $\text{depth}[i]$ 步结束后），红币在节点 $i$ 时所能获得的最大总分。
答案即为所有深度 $d$ 的节点中 $dp[i]$ 的最大值。

转移分析

考虑从深度 $h-1$ 转移到深度 $h$。设当前层（深度 $h$）的节点集合为 $L_h$。
对于 $i \in L_h$，上一步（深度 $h-1$）结束时红币在某个节点 $p$（$p$ 是 $i$ 的父节点或其它节点），蓝币在任意节点 $q$（深度 $h-1$）。
第 $h$ 步包含三个操作：

1. 红币移动到它的一个孩子（记为 $x$，$x \in L_h$）。
2. 蓝币移动到任意一个深度 $h$ 的节点（记为 $y$，$y \in L_h$）。
3. 可以选择交换两枚硬币。

最终红币在 $i$，蓝币在另一个节点，得分增加 $|a_{\text{红}} - a_{\text{蓝}}|$。

根据第三步是否交换，分为两种情况：

情况一：不交换

此时红币就是第一步移动到的节点，即 $i = x$。

• 上一步红币必须在 $i$ 的父节点 $\text{parent}[i]$（唯一）。
• 蓝币可以移动到任意 $y \in L_h$，得分 $|a_i - a_y|$。
• 上一步总分 $dp[\text{parent}[i]]$（红币在父节点时的最优值）。
• 蓝币的先前位置不影响本轮（因为本轮蓝币可以任意跳），所以本轮总分为

$$ dp[\text{parent}[i]] + \max_{y \in L_h} |a_i - a_y|. $$

由于 $\max_{y \in L_h} |a_i - a_y| = \max(a_i - \min L_h,\ \max L_h - a_i)$，其中 $\min L_h$ 和 $\max L_h$ 是当前层所有 $a$ 的最小值和最大值。
因此情况一的候选值为

$$\text{best1}(i) = dp[\text{parent}[i]] + \max(a_i - \min,\ \max - a_i). $$

情况二：交换

此时红币在第三步后变成了蓝币移动到的节点，即 $i = y$。

• 上一步红币在某个节点 $p$（深度 $h-1$），它有一个孩子 $x \in L_h$ 作为第一步的红币目标。
• 蓝币移动到 $y = i$。
• 交换后红币在 $i$，蓝币在 $x$，得分 $|a_x - a_i|$。
• 上一步总分 $dp[p]$，而 $p = \text{parent}[x]$。

因此对固定的 $i$，候选值为

$$\max_{x \in L_h} \big( dp[\text{parent}[x]] + |a_x - a_i| \big). $$

记 $\text{val}[x] = dp[\text{parent}[x]]$，则上式变为

$$M(i) = \max_{x \in L_h} \big( \text{val}[x] + |a_x - a_i| \big). $$

高效计算 $M(i)$

利用绝对值拆解：

$$\text{val}[x] + |a_x - a_i| = \max\big( (\text{val}[x] - a_x) + a_i,\ (\text{val}[x] + a_x) - a_i \big). $$

令

$$A = \max_{x \in L_h} (\text{val}[x] - a_x),\quad B = \max_{x \in L_h} (\text{val}[x] + a_x). $$

则对于任意 $i$，

$$M(i) = \max(A + a_i,\ B - a_i).$$

因此，对每一层，我们可以先遍历一次计算 $A$ 和 $B$，再遍历一次计算每个 $i$ 的 $M(i)$，时间复杂度 $O(|L_h|)$。

初始条件

深度 $0$ 只有根节点 $1$，我们设 $dp[1] = 0$（无得分），且根没有 $a$ 值（不参与绝对值计算）。
对于深度 $1$ 的节点 $i$，$\text{parent}[i] = 1$，$dp[\text{parent}[i]] = 0$，$\text{val}[x] = 0$，因此

$$\text{best1}(i) = \max(a_i - \min L_1,\ \max L_1 - a_i),\quad M(i) = \max_{x \in L_1} |a_x - a_i|, $$

两者相等，故 $dp[i] = \max_{y \in L_1} |a_i - a_y|$，符合直观。

算法步骤

1. 读入 $n$，建树，以 $1$ 为根进行 BFS/DFS，记录每个节点的父节点 $\text{parent}[i]$ 和深度 $\text{depth}[i]$，同时将同一深度的节点放入 vector 数组 nodes[h]。
2. 读入 $a_2 \dots a_n$，可忽略 $a_1$。
3. 初始化 $dp[1] = 0$。
4. 按深度 $h = 1, 2, \dots, d$ 依次处理：
   • 获取当前层节点列表 layer = nodes[h]。
   • 计算 $\min = \min_{i \in layer} a_i$，$\max = \max_{i \in layer} a_i$。
   • 对每个 $i \in layer$，计算$$\text{best1} = dp[\text{parent}[i]] + \max(a_i - \min,\ \max - a_i). $$
   • 初始化 $A = -\infty$，$B = -\infty$。
     对每个 $x \in layer$，计算 $\text{val} = dp[\text{parent}[x]]$，更新
     $A = \max(A,\ \text{val} - a_x)$，$B = \max(B,\ \text{val} + a_x)$。
   • 再次遍历 $i \in layer$，计算
     $M = \max(A + a_i,\ B - a_i)$，
     $dp[i] = \max(\text{best1},\ M)$。
5. 答案 $= \max_{i: \text{depth}[i]=d} dp[i]$。

复杂度

每层遍历常数次，总时间复杂度 $O(n)$，空间复杂度 $O(n)$。