题解：AT_arc098_d [ARC098F] Donation

· · 题解

给自己糖麻了。

首先显然的去建最小重构树。

考虑正难则反。

从终点出发，二分答案一个在终点交完税以后剩下的钱，于是变成回到上面的点去拿钱。

然后一路向上的点权（钱数限制）不降，手上拿的钱数不降，于是每次登上某个非叶子后就意味着子树内所有的钱都可以收到了。

那么我们从一个叶子开始就一路向上爬，爬到根就赢了。

check 直接这么做显然是 O(n^2) 还不算二分答案的复杂度，但是我们可以剪枝，你注意到一个点向上爬爬死了也就意味着其他的爬到这个被爬过的点，结局其实是一样的。

于是打个 vis 标记来剪枝，单次 check 复杂度秒变线性。

于是整体 O(n\log n)。

一个细节是，你往上爬的话父亲的贡献可以先吃到再去 check 是否符合准入标准，于是事实上这个边的边权会变成 A-B，于是你要按照这个新规则来跑重构树。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int a[N],b[N];
struct fish{
    int u,v,w,id;
};
vector<fish>vv;
bool cmp(fish x,fish y){
    return x.w-b[x.id]<y.w-b[y.id];
}
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int siz[N];
int fath[N];
int id[N];
int w[N];
bool vis[N];
int n,m,nn;
bool chk(int u,int x){
    if(x+siz[u]<w[u])return 0;
    while(u!=n){
        if(vis[u])return 0;
        if(x+siz[u]+b[id[fath[u]]]<w[fath[u]])
        return 0;
        vis[u]=1;
        u=fath[u];
    }
    return 1;
}
bool check(int x){
    memset(vis,0,sizeof vis);
    for(int i=1;i<=nn;i++)
    if(chk(i,x))return 1;
    return 0;
}
signed main(){
    cin>>n>>m;
    nn=n;
    for(int i=1;i<=n+n;i++)
    fa[i]=i;
    int sum=0;
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i],sum+=b[i],
    siz[i]=b[i],w[i]=a[i];
    if(n==1){
        cout<<max(a[1],b[1]);
        return 0;
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        vv.push_back({u,v,max(a[u],a[v]),(a[u]<a[v]?v:u)});
    }
    sort(vv.begin(),vv.end(),cmp);
    for(fish qwq:vv)
    if(find(qwq.u)!=find(qwq.v)){
        n++;
        qwq.u=find(qwq.u);
        qwq.v=find(qwq.v);
        siz[n]=siz[qwq.u]+siz[qwq.v];
        fath[qwq.u]=n;
        fath[qwq.v]=n;
        fa[qwq.u]=n;
        fa[qwq.v]=n;
        id[n]=qwq.id;
        w[n]=qwq.w;
    }
    int l=0,r=1e9;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<r+sum;
    return 0;
}
// 本题核心 trick：
// 我能让钱 反过来流
// 怎样 我有这个威能

thin ice 题解通道关了，难过。