AT_arc098_d [ARC098F] Donation 题解

zrl123456 · 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 即可，容易得到状态转移方程：

其中 siz_u 表示子树 u 内的 b_i 总和，\text{son}_u 表示 u 的儿子集合，特别地，对于叶子结点 u，满足 f_u=a_u+b_u。
这样我们直接 DP 就做完了这道题。
时空复杂度均为 \Theta(n+m)。

code