题目概述

小 E 有 n 个 AI 排成树形结构，每个 AI 有一道难度为 $d_i$ 的题目。
每次操作可以选择一个 AI，将它和所有与它直接相连的 AI 中的题目合并成一道新题，新题难度 = 相邻 AI 题目难度之和 − 该 AI 原有题目难度，然后相邻 AI 题目难度归零。

目标：经过 n−1 次操作，最终只剩一个 AI 有题目，且该题目难度尽量大。

问题转化

这实际上是一个树上合并问题，每次合并一个节点和它的所有邻居。

观察合并规则：

• 设当前节点 u 难度为 $a_u$，邻居难度和为 $S$
• 合并后新难度 = $S - a_u$
• 这相当于：$a_u$ 的系数从 +1 变为 −1，每个邻居系数从 +1 变为 0

最终目标：通过一系列合并，确定每个节点难度在最终表达式中的系数（+1 或 −1），使得加权和最大。

关键观察

1. 系数规律：

   • 每个节点难度在最终表达式中的系数只能是 +1 或 −1
   • 根节点系数必须为 +1（因为最后只剩它）
   • 对于任意节点，如果它的系数是 +1，那么它的父节点系数必须是 −1（因为合并时父节点系数会翻转）
   • 如果节点系数是 −1，父节点系数可以是 +1 或 −1

2. 状态设计： 设 $f[u][x][y]$ 表示以 u 为根的子树，u 的系数为 $x$（0 表示 −1，1 表示 +1），且子树内特殊结构状态为 y 时的最大总难度。

   y 的含义（本题解法的核心）：

   • y=0：正常情况
   • y=1：子树中存在某个节点 v，v 系数为 −1 且 v 的父节点系数为 +1（即存在“−1 接在 +1 下面”的结构）
   • y=2：子树根 u 的父节点系数为 +1 时，允许的特殊结构
   • y=3：子树根 u 的父节点系数为 −1 时，允许的特殊结构

3. 合并策略：

   • 对于每个子树，根据父节点系数和当前节点系数，决定如何合并子树的贡献
   • 需要维护 g[u] = 子树 u 的最大总难度
   • 需要维护 h[u] = 子树 u 在存在特殊结构时的最大总难度

算法核心

状态转移

对于节点 u：

1. 先计算所有子树的 sg[x] 和 sh[x]（x 表示 u 的系数）

   • sg[x] = Σ max(g[v], f[v][x][0])
   • sh[x] = Σ max(h[v], f[v][x][0])

2. 然后计算 f[u][x][y]：

   • y=0：取 sg[0] 和 sg[1] 的最大值
   • y=1：取 sh[x^1]
   • y=2,3：枚举哪个子树提供特殊结构，其他子树正常贡献

3. 最后加上当前节点的贡献：

   • 如果 x=1（系数 +1），加 $a_u$
   • 如果 x=0（系数 −1），减 $a_u$

最终答案

答案是 g[1]，即以 1 为根的整棵树的最大总难度。

复杂度分析

• 时间复杂度：$O(n)$
  每个节点处理时，对子节点的枚举是线性的，总体是树形 DP 的标准复杂度。
• 空间复杂度：$O(n)$
  存储树结构和 DP 数组。

样例解析

样例：

n = 4
d = [-1, 2, 3, 4]  
c = [1, 1, 1]  (树：1 是根，2,3,4 是儿子)

最优方案：

• 最终系数分配：1(−1), 2(+1), 3(+1), 4(+1)
• 计算：−(−1) + 2 + 3 + 4 = 1 + 2 + 3 + 4 = 10

验证操作顺序：

1. 合并节点 1：新难度 = (2+3+4) − (−1) = 10
2. 其他节点难度归零，只剩节点 1 有难度 10

代码关键点

// 状态定义：
// f[u][x][y] - 子树 u，u 系数为 x(0:-1,1:+1)，状态 y
// g[u] - 子树 u 的最大总难度  
// h[u] - 子树 u 在存在特殊结构时的最大难度

// 核心转移：
for (int v : e[u]) {
    dfs(v);
    for (int x = 0; x < 2; x++) {
        sg[x] += max(g[v], f[v][x][0]);
        sh[x] += max(h[v], f[v][x][0]);
    }
}

总结

这道题的关键在于：

1. 将操作序列转化为系数分配问题
2. 发现系数之间的约束关系（+1 的父节点必须是 −1）
3. 设计包含特殊结构状态的 DP 来处理树形约束
4. 高效合并子树信息，避免指数复杂度

这种"树上操作 → 系数分配 → 带状态树形 DP"的思路，在解决复杂树上合并问题时非常有效。