#PQJ2747x16453. QOJ 2747_16453

    ID: 2860 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HEOI 2015树上算法深搜

QOJ 2747_16453

河北省组队选拔赛 第一试 兔子与樱花 【题目细节】 sakura.cpp/.c/.pas/.in/.out 时间限制:1s 空间限制:256M

【问题描述】 很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所 在森林里的樱花树很特殊。樱花树由n 个树枝分叉点组成,编号从0 到n-1,这n 个分叉点 由n-1 个树枝连接,我们可以把它看成一个有根树结构,其中0 号节点是根节点。这个树的 每个节点上都会有一些樱花,其中第i 个节点有c_i 朵樱花。樱花树的每一个节点都有最大 的载重m,对于每一个节点i,它的儿子节点的个数和i 节点上樱花个数之和不能超过m, 即son(i) + c_i <= m,其中son(i)表示i 的儿子的个数,如果i 为叶子节点,则son(i) = 0 现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个 节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就 会继续向上连接,直到第一个没有被删除的节点为止。 现在兔子们希望计算在不违背最大载重的情况下,最多能删除多少节点。 注意根节点不能被删除,被删除的节点不被计入载重。

【输入格式】 从sakura.in 中读入 第一行输入两个正整数,n 和m 分别表示节点个数和最大载重 第二行n 个整数c_i,表示第i 个节点上的樱花个数 接下来n 行,每行第一个数k_i 表示这个节点的儿子个数,接下来k_i 个整数表示这个 节点儿子的编号

【输出格式】 输出到sakura.out 中。 一行一个整数,表示最多能删除多少节点。

【样例输入】 10 4 0 2 2 2 4 1 0 4 1 1 3 6 2 3 1 9 1 8 1 1

0 0 2 7 4 0 1 5 0

【样例输出】 4

【数据规模与约定】 对于30%的数据,1 <= n <= 5000, 1 <= m <= 100, 0 <= c_i <= 100 对于70%的数据,1 <= n <= 200000, 1 <= m <= 2000, 0 <= c_i <= 1000 对于100%的数据,1 <= n <= 2000000, 1 <= m <= 100000, 0 <= c_i <= 1000 数据保证初始时,每个节点樱花数与儿子节点个数之和大于0 且不超过m