解题思路

本题要求在花费不超过 x 的条件下，最小化所有路径权值的最大值。

核心观察

路径的权值上限 X 是否可行，可以通过贪心从后往前递推：

1. 对于终点 v，其所在路径的权值上限为 X，因此 a_v 必须不超过 X
2. 对于其他节点 u，从 u 出发的路径需要满足：a_u + max_child <= X
3. 从拓扑序的逆序递推，可以得到每个节点满足约束所需的最小点权
4. 计算总花费 sum(max(0, a_i - new_a_i) * c_i)，判断是否 <= x

算法步骤

1. 预处理拓扑序，建立反向图
2. 二分答案 X（上界可取所有 a_i 之和）
3. 对每个 X，从后往前递推计算每个节点的最小可行点权
4. 验证所需总花费是否 <= x
5. 二分找到最小的可行 X

时间复杂度

O((n + m) * log(sum a_i))，在 n <= 500 时完全可接受

参考实现 (Python)