bzoj4027[HEOI2015]兔子与樱花

http://www.lydsy.com/JudgeOnline/problem.php?id=4027

贪心。

我们发现，如果点i被删，那么它使父亲增加的重量为c[i]+son[i]-1

我们记val[i]=c[i]+son[i]-1

我们把删去的点染成灰色，发现其实这样的：

每个红色部分中，若干个被删去的点（灰色）和一个未删去的点（白色）组成了一棵树，这棵树合法当且仅当每个红色部分中val值的和小于等于M-1，即∑val<=M-1

我们可以用拟阵来证明贪心：

S={点_1,点_2,...,点_n-1,点_n}

L={x|x是S子集，表示灰色点的合法的集合}

遗传性：如果B∈L，那么任意的A⊆B，A必定满足A∈L。

证明：

因为B∈L，所以B中∑val<=M-1，又因为A⊆B，所以A中∑val必满足∑val<=M-1，所以A∈L。

交换性：如果A∈L，B∈L，且|A|<|B|，那么存在一个元素x∈B-A，满足A∪{x}∈L。

证明：

因为|A|<|B|，所以B中必定有一个A中没有的灰点，并且任选都能满足∑val<=M-1，所以成立。

所以可以用贪心了。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj
 
using namespace std;

typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b)  for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define SF scanf
#define PF printf
#define two(k) (1<<(k))

template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

const DB EPS=1e-9;
inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);

inline int gint()
  {
        int res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }
inline LL gll()
  {
      LL res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }

const int maxN=2000000;

int N,M;
int son[maxN+100],c[maxN+100];
vector<int> to[maxN+100];
int head,tail,que[maxN+100];
int val[maxN+100],ans;

struct cmp{inline bool operator () (int a,int b){return a>b;}};
priority_queue<int,vector<int>,cmp> Q;

int main()
  {
      freopen("bzoj4027.in","r",stdin);
      freopen("bzoj4027.out","w",stdout);
      int i,j;
      N=gint();M=gint();
      re(i,1,N)c[i]=gint();
      re(i,1,N)
        {
            son[i]=gint();
            re(j,0,son[i]-1){int v=gint()+1;to[i].push_back(v);}
        }
      re(i,1,N)val[i]=c[i]+son[i]-1;
      que[head=tail=1]=1;
      while(head<=tail)
        {
            int u=que[head++];
            re(i,0,son[u]-1)que[++tail]=to[u][i];
        }
      red(i,tail,1)
        {
            int u=que[i];
            while(!Q.empty())Q.pop();
            re(j,0,son[u]-1)Q.push(val[to[u][j]]);
            while(!Q.empty() && val[u]+Q.top()<=M-1)val[u]+=Q.top(),ans++,Q.pop();
        }
      cout<<ans<<endl;
      return 0;
  }