记录编号	197544	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015] 兔子与樱花	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	3.574 s
提交时间	2015-10-24 07:34:49	内存使用	40.36 MiB

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

bool vis[2000010];
int n,m,first[2000010],tot;
int ver[2000010],son[2000010],Ans;

struct Edge{
    int v,next;
}edge[2000010];

struct My_define{
    int id,w;
    friend bool operator < (My_define a,My_define b){
        return a.w>b.w;
    }
}temp,tmp;

void Add(int u,int v)
{
    edge[++tot].v=v;
    edge[tot].next=first[u];
    first[u]=tot;
}

void Tree_DP(int rt)
{
    if(!son[rt])return;
    priority_queue<My_define>q;
    while(!q.empty())q.pop();
    for(int i=first[rt];i!=-1;i=edge[i].next){
        Tree_DP(edge[i].v);temp.id=edge[i].v;
        temp.w=son[edge[i].v]+ver[edge[i].v];
        q.push(temp);
    }
    while(true){
        if(!q.empty()){
            temp=q.top();q.pop();
            if(son[rt]+ver[rt]+temp.w-1<=m){
                vis[temp.id]=1;Ans++;
                ver[rt]+=ver[temp.id];
                son[rt]+=son[temp.id]-1;
                continue;
            }
            else break;
        }
        else break;
    }
}

int main()
{
	freopen("sakura.in","r",stdin);
	freopen("sakura.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)first[i]=-1;
    for(int i=0;i<n;i++)scanf("%d",&ver[i]);
    for(int i=0;i<n;i++){
        scanf("%d",&son[i]);
        for(int j=1,v;j<=son[i];j++){
            scanf("%d",&v);
            Add(i,v);
        }
    }Tree_DP(0);
    printf("%d",Ans);
}