自动搬运

查看原文

来自洛谷，原作者为

	YoungNeal **

搬运于2025-08-24 21:56:34，当前版本为作者最后更新于2018-05-24 19:21:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解在博客食用效果更佳哦~

Solution

做法：自底向上，贪心的优先删除每个点的儿子中代价最小的一个。

贪心：以 $sons[i]+c[i]$ 为 $i$ 点的代价，每个点我们选取代价最小的删除，结果一定不会变差。

证明：对于 $i$ 点和 $i$ 的两个儿子 $j,p$，假设 $c[j]+sons[j]<c[p]+sons[p]$，由决策包容性，选 $j$ 优先删除一定比选 $p$ 优先删除更优。

自底向上：从根节点 $dfs$ ，从叶子结点向上回溯。路上如果遇到能删除的点就删，不必考虑其祖先。

证明：设点 $i$ 的儿子是 $j$ ，$j$ 的兄弟是 $p$ ，$j$ 还有一个儿子是 $q$。

$dfs$ 的过程中，如果在回溯到 $j$ 的时候发现可以删除 $q$，那么就删除 $q$，并更新 $j$ 本身的代价，这样可能会导致无法再回溯到 $i$ 点的时候删除 $p$。

粗略想一下这不是有后效性嘛，但是因为贪心删了儿子而导致这个点不能再删，那么我们只会损失一个点，就是该点，而删除儿子至少会删除一个，所以不会亏。。

综上，自底向上的删除无后效性，满足贪心性质。

Code

#include<map>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 2000005

int n,m;
int ans;
int c[N];
int sons[N],cnt;
int tot[N],l[N],r[N];

inline char nc(){
    static const int BS=1<<22;
    static unsigned char buf[BS],*st,*ed;
    if(st==ed) ed=buf+fread(st=buf,1,BS,stdin);
    return st==ed?EOF:*st++;
}
//#define nc getchar
inline int getint(){
    char ch;
    int res=0;
    while(!isdigit(ch=nc()));
    while(isdigit(ch)){
        res=(res<<1)+(res<<3)+(ch^48);
        ch=nc();
    }
    return res;
}

bool cmp(int a,int b){
    return sons[a]+c[a]<sons[b]+c[b];
}

void dfs(int now){
    if(!sons[now]) return;
    for(int i=l[now];i<=r[now];i++)
        dfs(tot[i]);
    std::sort(tot+l[now],tot+r[now]+1,cmp);
    for(int i=l[now];i<=r[now];i++){
        if(c[tot[i]]+sons[tot[i]]+c[now]+sons[now]-1<=m){
            ans++;
            c[now]+=c[tot[i]];
            sons[now]+=sons[tot[i]]-1;
        }
        else break;
    }
}

signed main(){
    n=getint(),m=getint();
    for(int i=1;i<=n;i++)
        c[i]=getint();
    for(int i=1;i<=n;i++){
        sons[i]=getint();
        l[i]=cnt+1;
        r[i]=cnt+sons[i];
        for(int j=1;j<=sons[i];j++){
            int a=getint()+1;
            tot[++cnt]=a;
        }
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}