记录编号	552971	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015] 兔子与樱花	最终得分	100
用户昵称	fw	是否通过	通过
代码语言	C++	运行时间	3.871 s
提交时间	2020-08-09 21:30:09	内存使用	67.06 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read () {//快读  简单版 （没判断负数） 
	int s = 0;
	char ch = getchar ();
	while (ch < '0' || ch > '9') ch = getchar ();
	while (ch >= '0' && ch <= '9') s = (s << 3) + (s << 1) + ch - '0',ch = getchar ();
	return s;                        
}
const int MAXN = 2000001;
vector <int> c[MAXN];//数组 

int w[MAXN]; // w[i] 存储节点 i 的重量 
bool cmp (int a,int b) { return w[a] < w[b]; }
int n,W;
int ans = 0;
void dfs (int u) {
	for (int q = 0;q < c[u].size();++ q) {
		dfs (c[u][q]);
	}
	sort (c[u].begin(),c[u].end(),cmp);
	w[u] += c[u].size();
	for (int q = 0;q < c[u].size();++ q) {  //排好序了，从小到大 
		if (w[u] + w[c[u][q]] - 1 > W) break;
		w[u] += w[c[u][q]] - 1,ans ++; 
	}
	return ;
} 
int main () {
	freopen("sakura.in","r",stdin);
	freopen("sakura.out","w",stdout);
	n = read ();
	W = read ();
	for (int q = 0;q < n;++ q) {  // 0 是根节点 
		w[q] = read ();
	}
	int nc,nc_x;
	for (int q = 0;q < n;++ q) {
		nc = read ();
		while (nc --) {
			nc_x = read ();
			c[q].push_back(nc_x);  //邻接表存储
		}
	}
	dfs (0);
	printf ("%d\n",ans);
	return 0;
}