这个题，我们可以发现，这就是个蛇皮的贪心。。。QAQ。。。

记录下来当前点的子节点，按照子节点的子节点个数，从少到多贪心。。。

呆码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 2000020
using namespace std;

int a[maxn],c[maxn],k[maxn],l[maxn],r[maxn];
int n,m,cnt,ans;

inline bool cmp(int x,int y)
{
    return c[x]<c[y];
}

inline void dfs(int now)
{
    for(int i=l[now];i<=r[now];i++) dfs(a[i]);
    c[now]+=k[now];
    sort(a+l[now],a+r[now]+1,cmp);
    for(int i=l[now];i<=r[now];i++)
    {
        if(c[now]+c[a[i]]-1<=m) c[now]+=c[a[i]]-1,ans++;
        else break;
    }
}

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

代码

转载于:https://www.cnblogs.com/zzzyc/p/9213086.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/96193194

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。