Description
很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由 (n) 个树枝分叉点组成，编号从 (0) 到 (n-1)，这 (n) 个分叉点由 (n-1) 个树枝连接，我们可以把它看成一个有根树结构，其中 (0) 号节点是根节点。这个树的每个节点上都会有一些樱花，其中第 (i) 个节点有 (c_i) 朵樱花。樱花树的每一个节点都有最大的载重 (m)，对于每一个节点 (i)，它的儿子节点的个数和 (i) 节点上樱花个数之和不能超过 (m)，即 (son(i) + c_i leq m)，其中 (son(i)) 表示 (i) 的儿子的个数，如果 (i) 为叶子节点，则 (son(i) = 0)
现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。
注意根节点不能被删除，被删除的节点不被计入载重。
Input
第一行输入两个正整数，(n) 和 (m) 分别表示节点个数和最大载重
第二行 (n) 个整数 (c_i) ，表示第 (i) 个节点上的樱花个数
接下来 (n) 行，每行第一个数 (k_i) 表示这个节点的儿子个数，接下来 (k_i)个整数表示这个节点儿子的编号
Output
一行一个整数，表示最多能删除多少节点。
Hint
对于 (30\%) 的数据，(1leq nleq 5000, 1leq mleq 100, 0leq c_ileq 100)
对于 (70\%) 的数据，(1leq nleq 200000, 1leq mleq 2000, 0leq c_ileq 1000)
对于 (100\%) 的数据，(1leq nleq 2000000, 1leq mleq 100000, 0leq c_ileq 1000)
数据保证初始时，每个节点樱花数与儿子节点个数之和大于 (0) 且不超过 (m)
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
",ans);
return 0;
}