CF533A Berland Miners

线段树维护区间 min

---

题意

给定 $n$ 个节点根为 $1$ 的有根树，每个节点有一个高度 $h_i$ ，另有 $k$ 个人，每个人有一个高度 $s_i$ ,一个人能从节点 $x$ 走到根当且仅当 $x$ 到根的路径上的所有节点的高度都不小于该人的高度。现有一次操作可以将一个节点的高度增加 $x$ ，代价为 $x$ ，问能否通过最多一次操作使得能给每个人分配一个起点（同一个节点最多只能被分配给一个人），使得每个人都能从起点走到根。
其中 $1 \leq n \leq 5 \cdot 10^5, 1 \leq h_i, s_i \leq 10^9, 1 \leq k \leq n$ 。

思路

若不考虑修改操作，只考虑原树的合法性。定义 $cnt_i$ 为将 $s_i$ 降序排序后能够作为第 $i$ 个人的起点的节点个数，则原树合法当且仅当对于 $\forall i \in [1, k]$ 有 $cnt_i \geq i$ ，其中 $cnti_i$ 可以通过一次差分预处理出来。
若考虑修改操作。若对于 $\forall i \in [1, k]$ 有 $cnt_i \geq i$ 初始即成立，则 $ans = 0$ ，否则修改操作一定是找到第一个满足 $cnt_i < i$ 的 $i$ ，将某个 $h < s_i$ 的节点高度改为 $s_i$ ，因为若有多个满足 $cnt_i < i$ 的 $i$ ，一定是更改最小的 $i$ 影响的范围最大，且若修改后值大于 $s_i$ 则不会使答案更优。
那么考虑合法的被修改节点 $x$ 的影响范围和它需要满足的条件为：

• $x$ 的影响范围为它为根的子树。
• $x$ 到根的路径上的点的高度均不小于 $s_i$ ，因为若存在小于 $s_i$ 的高度，则修改了 $x$ 节点也不会起作用。
• 由上一条件可以得到若 $x$ 满足条件，则 $x$ 子树中的节点均不满足条件。

显然可以得出满足条件的 $x$ 节点为若干个互相不互为祖先的节点，作用范围为它们的子树。因为互相没有祖先关系，它们的子树也互不相交， $dfs$ 找到所有满足条件的节点 $x$ 并暴力修改它们的子树对 $cnt$ 的贡献并开一个线段树维护 $cnt_i - i$ 的最小值是否大于 $0$ 即可，最多修改不会超过 $O(n)$ 次，所以总复杂度为 $O(n \cdot logn)$ 。
实际上修改 $x$ 的子树时若遇到节点的 $h < s_i$ 则可以直接退出，但遍历完也不会影响。

代码

/*
    Author: Cupids_Bow
    Time: 2022-08-11 09:46:09
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int N=5e5+5;

vector<int> e[N];
int n,K;
int h[N],s[N];
int pos[N];
int ans=1e9;
struct tree{
    int l[N<<2];
    int r[N<<2];
    int lz[N<<2];
    int minn[N<<2];
    void pushup(int x){
        minn[x]=min(minn[x<<1],minn[x<<1|1]);
    }
    void build(int x,int L,int R){
        l[x]=L;
        r[x]=R;
        if(L==R){
            minn[x]=-L;
            return;
        }
        int mid=L+R>>1;
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        pushup(x);
        return;
    }
    void pushdown(int x){
        if(lz[x]){
            int k=lz[x];
            minn[x<<1]+=k;
            lz[x<<1]+=k;
            minn[x<<1|1]+=k;
            lz[x<<1|1]+=k;
            lz[x]=0;
        }
        return;
    }
    void add(int x,int L,int R,int k){
        if(L>R) return;
        if(l[x]>=L&&r[x]<=R){
            minn[x]+=k;
            lz[x]+=k;
            return;
        }
        pushdown(x);
        if(r[x<<1]>=L) add(x<<1,L,R,k);
        if(l[x<<1|1]<=R) add(x<<1|1,L,R,k);
        pushup(x);
        return;
    }
    int find(int x){
        if(l[x]==r[x]) return l[x];
        pushdown(x);
        if(minn[x<<1]<0) return find(x<<1);
        else return find(x<<1|1);
    }
}tr;

void dfs(int x,int fa,int minn){
    pos[x]=[&]{
        int l=1,r=K,res=K+1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[mid]<=minn) res=mid,r=mid-1;
            else l=mid+1;
        }
        return res;
    }();
    for(auto v:e[x]){
        if(v==fa) continue;
        dfs(v,x,min(minn,h[v]));
    }
}

void add(int x,int fa,int minn){
    int poss=[&]{
        int l=1,r=K,res=K+1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[mid]<=minn) res=mid,r=mid-1;
            else l=mid+1;
        }
        return res;
    }();
    tr.add(1,pos[x],K,-1);
    tr.add(1,poss,K,1);
    for(auto v:e[x]){
        if(v==fa) continue;
        add(v,x,min(minn,h[v]));
    }
}

void del(int x,int fa,int minn){
    int poss=[&]{
        int l=1,r=K,res=K+1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[mid]<=minn) res=mid,r=mid-1;
            else l=mid+1;
        }
        return res;
    }();
    tr.add(1,pos[x],K,1);
    tr.add(1,poss,K,-1);
    for(auto v:e[x]){
        if(v==fa) continue;
        del(v,x,min(minn,h[v]));
    }
}

void dp(int x,int fa,int minn,int poss){
    if(minn<s[poss]) return;
    if(h[x]<s[poss]){
        add(x,fa,s[poss]);
        if(tr.minn[1]>=0) ans=min(ans,s[poss]-h[x]);
        del(x,fa,s[poss]);
        return;
    }
    for(auto v:e[x]){
        if(v==fa) continue;
        dp(v,x,min(minn,h[x]),poss);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    cin>>K;
    for(int i=1;i<=K;i++) cin>>s[i];
    sort(s+1,s+1+K,greater<int>());
    tr.build(1,1,K);
    dfs(1,1,h[1]);
    for(int i=1;i<=n;i++) tr.add(1,pos[i],K,1);
    if(tr.minn[1]>=0){
        cout<<"0";
        return true&&false;
    }
    int poss=tr.find(1);
    dp(1,1,1e9,poss);
    if(ans==1e9) ans=-1;
    cout<<ans;

    return true&&false;
}