题目概述

有 $n$ 个点带点权的树和 $m$ 个物品，一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点权改大，求至少改多少能使得所有物品都能放进树中。

解题报告

先不管把点权改大这个操作，我们考虑如何判断一个状态是否合法，会发现就是个二分图匹配问题……和这道题差不多。所以我们可以用线段树维护 $num_i-i$ 的最小值（ $i$ 是物品按照从大到小的顺序，$num_i$ 表示物品 $i$ 能够放进去的节点个数），如果最小值 $\ge 0$ 就验证成功。

于是枚举改 $x$ 点，然后二分改多少，改完之后，所有以 $x$ 点为最小值的点都可能发生了变化，需要进行修正。

但是这样复杂度不会爆炸吗？因为每个点最小值只有一个，所以所有点均修正一次是 $O(n)$ 的！

这样就可以得到一个 $O(nlog_2nlog_2S)$ 的算法，恭喜你爆炸了……

因此要想办法优化……我们会发现，只可能把权值修改成物品中出现过的权值，又因为最大的不满足的物品必须需要找到一个地方放，所以只可能会把权值修改成最大的不满足的物品的权值。

因此就可以 $O(nlog_2n)$ 解决啦。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const int maxn=500000;

int n,m,a[maxn+5],b[maxn+5],MIN[(maxn<<2)+5],tag[(maxn<<2)+5],ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],IA[maxn+5],IB[maxn+5];
struct data{
    int MIN,ID,lst;data() {}
    data(int a,int b,int c) {MIN=a;ID=b;lst=c;}
}s[maxn+5];vector<int> v[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
#define Pushup(p) (MIN[p]=min(MIN[(p)<<1],MIN[(p)<<1|1]))
void Build(int L,int R,int p=1){
    tag[p]=0;if (L==R) {MIN[p]=L-m-1;return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void Addtag(int p,int k) {MIN[p]+=k;tag[p]+=k;}
inline void Pushdown(int p){
    if (!tag[p]) return;int now=tag[p];tag[p]=0;
    Addtag(p<<1,now);Addtag(p<<1|1,now);
}
void Insert(int L,int R,int k,int l=1,int r=m,int p=1){
    if (L==l&&r==R) return Addtag(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int L,int R,int l=1,int r=m,int p=1){
    if (L==l&&r==R) return MIN[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return min(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
inline int Find(int x,int L=1,int R=m){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        x>=b[mid]?L=mid+1:R=mid-1;return R;
}
inline data Miner(data a,const data &b){
    if (b.MIN<=a.MIN) a.lst=a.MIN,a.MIN=b.MIN,a.ID=b.ID; else if (b.MIN<a.lst) a.lst=b.MIN;
    if (b.lst<a.lst) a.lst=b.lst;return a;
}
void Dfs(int x,int pre=0){
    s[x]=Miner(s[pre],data(a[x],x,2e9));v[s[x].ID].pb(x);
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    readi(m);for (int i=1;i<=m;i++) readi(b[i]);sort(b+1,b+1+m);Build(1,m);s[0]=data(2e9,-1,2e9);Dfs(1);
    for (int i=1;i<=n;i++) if (IB[i]=Find(s[i].lst),IA[i]=Find(s[i].MIN)) Insert(1,IA[i],1);
    if (MIN[1]>=0) return puts("0"),0;int lst;for (lst=m;lst;lst--) if (Ask(lst,m)<0) break;ans=2e9;
    for (int i=1;i<=n;i++){
        if (a[i]>=b[lst]) continue;int si=v[i].size();if (!si) continue;
        for (int j=0,x;j<si;j++){
            x=v[i][j];if (IA[x]) Insert(1,IA[x],-1);
            int now=min(lst,IB[x]);if (now) Insert(1,now,1);
        }if (MIN[1]>=0) ans=min(ans,b[lst]-a[i]);
        for (int j=0,x;j<si;j++){
            x=v[i][j];if (IA[x]) Insert(1,IA[x],1);
            int now=min(lst,IB[x]);if (now) Insert(1,now,-1);
        }
    }ans==2e9?puts("-1"):printf("%d\n",ans);return 0;
}