本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-24 21:41:34

:::::info[题目基本信息] 考察：Kruskal 重构树，并查集，动态规划 DP（$3189$）。
题目简介：
给定一个 $n$ 个点 $m$ 条边的无向联通图，你可以在这个图上任意选起点任意游走，唯一的限制是给定序列 $\{a_n\}$，当你在 $u$ 点时你的能力值不得小于 $a_u$。
现在你的任务是在每个节点都操作一次，当你位于 $u$ 点时你可以对 $u$ 点进行操作，操作后你的能力值会减少 $b_u$，当你能力值小于 $0$ 时任务立即失败（即使你操作了最后一个点），问任务成功需要的最低初始能力值是多少。
数据范围：

• $1\le n\le 10^5$
• $n-1\le m\le 10^5$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^9$ ::::: 先令 $a_u\leftarrow\max(a_u-b_u,0)$，限制转化为你在任一时刻位于点 $u$ 时能力值均不能低于 $a_u$。
  你考虑 $u$ 到 $v$ 如何才能最可能走过去，设 $u$ 和 $v$ 之间的一条路径为 $P$，当前能力值为 $p$，那么充要条件就为 $\max_{u\in P}a_u\le p$，现在我们就是尽可能得让这个值变小。
  让 $\max$ 变小我们可以考虑使用 Kruskal 重构树，但是现在是点权，所以我们考虑给所有的 $u$ 和 $v$ 连一条边，边权为 $\max(a_u,a_v)$，这样就可以跑最小生成树。
  考虑贪心，按 $a_u$ 从小到大枚举点 $u$，在和它相连的比 $a_u$ 小的点 $v$ 中没连的点令其与 $u$ 连边，正确性易证。
  这样我们建出了一棵最小生成树，但是通过尝试我们发现它的性质还是不够好，我们仍然无法解决这个问题。
  下面就是这个题非常妙的转化，我们将上面的建树方式转化为：

按 $a_u$ 从小到大枚举点 $u$，在和它相连的比 $a_u$ 小的点 $v$ 中没连的点令其最高的祖先与 $u$ 连边。

虽然看起来很人类智慧，但是正确性是成立的，因为与 $v$ 直接相连或间接相连的点 $w$ 的 $a_w$ 肯定都不超过 $a_u$，同时这条 $v$ 到 $w$ 路径上的权值肯定都不超过 $a_u$，所以点权 $\max$ 是不变的，正确性成立。
那么这样建树有没有什么其他性质呢？

• 性质：若以 $a_i$ 最大的 $i$ 为根，那么对于任意 $u,v$，若 $u$ 是 $v$ 的祖先，那么 $a_u>a_v$。证明显然。

那么有了这个重要性质这个题就可做了，容易发现本题在哪里选起点都无所谓，钦定从根开始，设 $f_u$ 表示以 $u$ 为根的子树中从 $u$ 开始操作完所有子树内的点（不必回到 $u$ 点）的最小初始能力值。那么对于一个 $u$，枚举最后进入的子树的根为 $v$，那么遍历其它子树时由于上面所说性质，我们只需保证最后一次回到 $u$ 时的能力值不低于 $a_u$ 即可，容易得到状态转移方程：
$$f_u=\min_{v\in\text{son}_u}(siz_u-siz_v+\max(a_u,f_v))$$ 其中 $siz_u$ 表示子树 $u$ 内的 $b_i$ 总和，$\text{son}_u$ 表示 $u$ 的儿子集合，特别地，对于叶子结点 $u$，满足 $f_u=a_u+b_u$。
这样我们直接 DP 就做完了这道题。
时空复杂度均为 $\Theta(n+m)$。

code