题目理解

我们有一个树形结构的聚变反应炉，每个节点（聚能块）有两个属性：

• $d_i$：激发所需的初始能量
• $c_i$：激发后向邻居传递的能量

当一个聚能块被激发时，它会向所有未被激发的邻居传递 $c_i$ 能量。这些传递的能量可以用于减少邻居激发所需的初始能量。

目标：找到激发所有聚能块所需的最小总能量。

---

关键观察

1. 激发顺序的影响

由于能量传递机制，激发顺序会影响总能量消耗：

• 如果先激发 $c_i$ 大的节点，它可以为多个邻居提供能量
• 如果先激发 $d_i$ 小的节点，可能节省初始投入

2. 能量传递规则

设节点 $u$ 被激发时：

• 对每个未被激发的邻居 $v$，$v$ 的所需能量减少 $c_u$
• 如果减少后 $d_v \leq 0$，则 $v$ 可以"免费"激发
• 能量传递只发生在激发时刻，且只影响当前未被激发的邻居

---

问题分析

这是一个在树结构上的最优激发顺序问题。我们需要确定一个激发顺序，使得总的外部能量投入最小。

设激发序列为 $p_1, p_2, \dots, p_n$，则总能量消耗为： [ \sum_{i=1}^n \max\left(0, d_{p_i} - \sum_{j=1}^{i-1} [p_j \in N(p_i)] \cdot c_{p_j}\right) ] 其中 $N(p_i)$ 表示 $p_i$ 的邻居集合。

---

动态规划思路

对于树形结构，自然的想法是使用树形DP。

状态设计

设 $dp[u][s]$ 表示以 $u$ 为根的子树，在父节点的激发状态为 $s$ 时的最小能量消耗。

但是父节点的激发状态会影响子树的能量需求，这使得状态设计比较复杂。

---

贪心策略

观察发现，对于每个节点，我们面临一个选择：

1. 花费 $d_u$ 能量直接激发它
2. 依靠邻居的传递来减少甚至免除激发成本

重要性质：

• 如果 $c_i \geq d_i$，那么只要有一个邻居被激发，这个节点就可以免费激发
• 如果 $c_i < d_i$，那么即使所有邻居都被激发，仍然需要额外能量 $d_i - \sum_{v \in N(u)} c_v$

---

分类讨论

Case 1: $c_i = 0$

此时没有能量传递，必须为每个节点支付 $d_i$ 能量。 [ \text{答案} = \sum_{i=1}^n d_i ]

Case 2: $c_i = 1$ 且 $d_i = 1$

如样例所示，可能只需要激发一个节点就能连锁激活所有节点。

Case 3: 一般情况

需要设计更复杂的策略。

---

算法设计

方法：树形DP + 贪心排序

对于以 $u$ 为根的子树，考虑两种决策：

1. 先激发父节点：父节点的 $c$ 值可以传递给所有子节点
2. 后激发父节点：子节点的 $c$ 值可以传递给父节点

我们定义状态 $dp[u]$ 表示激发以 $u$ 为根的子树所需的最小能量（不考虑父节点的传递）。

状态转移：

1. 收集所有子节点 $v$ 的 $dp[v]$ 值
2. 对于每个子节点，计算如果父节点先激发能给子节点带来的收益
3. 对子节点按照某种贪心顺序排序，决定激发顺序

贪心排序规则：

对于两个节点 $i$ 和 $j$，比较它们作为父节点和子节点的相对收益：

• 如果 $c_i \geq d_i$ 且 $c_j < d_j$，优先激发 $i$（因为 $i$ 可能免费激活）
• 否则，比较 $\min(d_i, c_i)$ 和 $\min(d_j, c_j)$ 的比值

---

样例验证

输入：

5
1 1 1 1 1
1 1 1 1 1
1 2
2 3
3 4
4 5

过程：

• 所有 $d_i = 1$, $c_i = 1$
• 激发任意一个节点（花费1）
• 该节点激发后为邻居提供1能量，正好满足邻居的需求
• 连锁反应激活所有节点
• 总能量 = 1

输出：1 ✓

---

优化策略

对于特殊情况的优化：

1. 所有 $c_i = 0$： [ \text{答案} = \sum d_i ]

2. 所有 $c_i = 1$ 且 $d_i = 1$：

   • 答案为1（只要激发一个节点）

3. 树是链的情况：

   • 可以从端点开始贪心

4. 所有 $c_i$ 相等：

   • 可以简化比较函数

---

复杂度分析

• 树形DP：$O(n)$
• 排序：$O(n \log n)$（每个节点对子节点排序）
• 总复杂度：$O(n \log n)$，对于 $n \leq 10^5$ 可接受

---

总结

本题的关键在于：

1. 理解能量传递的机制和激发顺序的重要性
2. 设计合适的贪心策略来决定激发顺序
3. 利用树形DP在树结构上进行最优决策
4. 处理各种特殊情况

这是一个典型的树形DP+贪心问题，考察了对树结构的理解和贪心策略的设计能力。实际实现时可能需要根据具体数据范围调整策略。