AtCoder

Luogu

分析

设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。

然后可以发现两个结论：

• 每个点只会在最后一次访问时被捐赠。
• $c_i$ 大的会优先捐赠。

那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$ 个，然后捐赠 $u$，最后捐赠剩下的一个。

可以发现这其实是一个树形结构，而这棵树可以把所有点按 $c_i$ 从小到大排序后用并查集维护每个点所属联通块来建出。

这样子就可以考虑树形 DP 了。设 $dp_i$ 表示捐赠点 $i$ 和它的所有子树至少需要多少円，$sum_i$ 表示 $i$ 子树中所有点的 $b_i$ 之和，枚举最后捐赠的子树可以得到
$$
dp_u=\min\left\{sum_u-sum_v+\max\left\{dp_v,c_u\right\}\right\}
$$
$u$ 为叶子时为边界，显然有 $dp_u=\max\left\{a_u,b_u\right\}$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,a[N],b[N],c[N],p[N],rk[N];
vector<int> G[N],E[N];
bool cmp(int x,int y) { return c[x]<c[y]; }

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

ll dp[N],sum[N];
void dfs(int u) {
    sum[u]=b[u],dp[u]=1e18;
    if (E[u].empty()) { dp[u]=max(a[u],b[u]); return; }
    for (int v:E[u]) dfs(v),sum[u]+=sum[v];
    for (int v:E[u])    
        dp[u]=min(dp[u],sum[u]-sum[v]+max(1ll*c[u],dp[v]));
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) a[i]=read(),b[i]=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read();
        G[u].emplace_back(v),G[v].emplace_back(u);
    }
    for (int i=1;i<=n;++i) c[i]=max(0,a[i]-b[i]),p[i]=i;
    sort(p+1,p+n+1,cmp);
    for (int i=1;i<=n;++i) rk[p[i]]=f[i]=i;
    for (int i=1;i<=n;++i)
        for (int v:G[p[i]])
            if (find(v)!=p[i]&&rk[v]<i)
                E[p[i]].emplace_back(find(v)),f[find(v)]=p[i];
    dfs(p[n]); printf("%lld\n",dp[p[n]]);
    return 0;
}