ARC098D Donation

题意：给出一张 个点 条边的无向连通图。

点 有两参数 。当你经过该点时，必须至少拥有 元，在该点打卡需要花费 元。

你可以从任意点开始旅程。你需要在所有点打卡一次，问初始时最少需要携带多少元。

，时限 。

---

很有意思的一个题。

• 性质：在某点打卡后必不会再次访问某点。

  解释：不难发现，旅行中的钱数是单调不增的。

  若两次访问某点，第一次不打卡，第二次打卡要比第一次就打卡优，因为中间的一段路程余钱更多。

若遵守上述策略，令 ，约束可以等价于：在 点的所有时刻钱数都 。

一种直观的想法是：按照 排序，并按顺序打卡。

可惜的是，在点之间移动时，受到图的限制，途中可能经过 更大的节点。

我们将 的边权设为 ，求最小生成树，不难发现最优的移动路径只会在最小生成树上，这样就把图简化成了树。

最小生成树的性质仍然不够好（边上的 是乱序的），考虑建立重构树。

观察边权的性质，根据 ，建树的过程等价于按照 从小到大枚举点 ，然后尽量加入和 更小的点 连接的边。

我们连边 （ 目前的最浅祖先）。这样就建立了类似重构树的结构，满足下面两条关键性质 ：

• 深度越深， 越小。

• 两点间路径的 取得最小值。

接下来在树上 。

设 为处理完 子树（不必回到 ）所需的初始钱数， 为子树内 的和。

对于叶节点，显然有 。

对于非叶节点，若有 个子树，要先处理 个，然后在 打卡，然后处理最后一个。

在处理前面 个时，由于树中的 上大下小，而钱单调不增，所以只需要考虑在 打卡的一次约束。

枚举最后进入的子树 ，则有 其中， 是处理前面 个子树的花费， 是后面的限制。