质量很大，孩子很喜欢?
上来就感觉很神秘，要决策的东西有点多，起点，交钱，还有每个点的限制，应该没法做。
所以直接考虑倒过来，假设我们最后还剩下 \(w\) 元，去判断能不能反着跑完。如果能跑完答案就是 \(w+\sum b\)。
一开始其实并不知道这样对不对，先看一看有没有更好的条件。假设一开始选了一个点 \(u\)，那么肯定要满足 \(w+b_u\ge a_u\) 也就是 \(w\ge a_u-b_u\)。发现对于其它节点都是类似的，走到节点 \(x\) 时 \(w\) 一定要大于等于 \(a_x-b_x\) 才行。
如果我们确定了下一个要走到的点 \(x\) 那肯定会一路走 \(a-b\) 最小的点对吧，这是一个比较经典的模型，一条边 \((u,v)\) 的边权设为 \(\max(a_u-b_u,a_v-b_v)\) 然后跑 Kruskal 最小生成树的重构树即可。转化成了一个树上问题就舒服很多。
回到上面这个问题，我们选了一个点 \(u\)，再走到其它点一定会经过它的重构树上父亲 \(fa_u\)，那么此时 \(fa_u\) 整颗子树内最严格的限制肯定是满足了，根据贪心策略我们肯定是要把 \(fa_u\) 子树内叶子的 \(b\) 值全取上然后再往父亲跳。
根据这个策略不难发现，如果要从 \(u\) 开始走完全部点，一定满足 \(u\) 到重构树根这条链上的每个点 \(x\) 都有 \(w+s_x\ge a_{fa_x}-b_{fa_x}\)，其中 \(s_x\) 表示 \(x\) 子树内的 \(\sum b\)。注意叶子节点还有一个限制是 \(w\ge a_u-b_u\)。所以我们知道 \(w=\max(\{a_{fa_x}-b_{fa_x}-s_x\},a_u-b_u)\)。对于每个叶子节点都求一边就行。时间复杂度 \(\mathcal O(n+m\log m)\)。
忘了叶子节点还有那个限制调了一年 /oh。代码比较简短。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using i64 = long long;
using u64 = unsigned long long;
using pii = std::pair<int,int>;
constexpr int maxn = 2e5 + 5;
constexpr i64 infll = 1e16;
struct edge {
int u, v;
i64 w;
edge() { u = v = w = 0; }
edge(int u, int v, i64 w) : u(u), v(v), w(w) {}
} E[maxn];
int n, m, pre[maxn], cnt;
i64 s[maxn], ans[maxn], a[maxn];
std::vector<int> G[maxn];
void chkmax(i64& x, i64 y) { if (y > x) x = y; return ; }
void chkmin(i64& x, i64 y) { if (y < x) x = y; return ; }
int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%lld %lld", &a[i], &s[i]), a[i] = std::max(a[i] - s[i], 0ll);
std::iota(pre + 1, pre + 2 * n, 1); cnt = n;
for (int i = 1; i <= m; ++i) {
int u, v; scanf("%d %d", &u, &v);
E[i] = edge(u, v, std::max(a[u], a[v]));
}
std::sort(E + 1, E + 1 + m, [&](const edge& lhs, const edge& rhs) {
return lhs.w < rhs.w;
});
for (int i = 1; i <= m; ++i) {
int u = find(E[i].u), v = find(E[i].v);
if (u == v) continue ;
pre[u] = pre[v] = ++cnt;
s[cnt] = s[u] + s[v]; a[cnt] = E[i].w;
G[cnt].pb(u); G[cnt].pb(v);
if (cnt >= 2 * n - 1) break ;
}
i64 res = infll; assert(cnt == 2 * n - 1);
for (int i = cnt; i; --i) {
if (i <= n) { chkmin(res, std::max(ans[i], a[i])); continue ; }
for (auto& v : G[i])
chkmax(ans[v] = ans[i], a[i] - s[v]);
}
printf("%lld\n", res + s[cnt]);
return 0;
}