BZOJ4027 - Click Here
Description
很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由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。
现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。
注意根节点不能被删除，被删除的节点不被计入载重。
Input
第一行输入两个正整数，n和m分别表示节点个数和最大载重
第二行n个整数c_i，表示第i个节点上的樱花个数
接下来n行，每行第一个数k_i表示这个节点的儿子个数，接下来k_i个整数表示这个节点儿子的编号
Output
一行一个整数，表示最多能删除多少节点。
Solutions
某个节点载重的定义为樱花数+儿子数，而删除某个节点后，会传递樱花数和儿子数，仅损失被删除的节点。如果我们给每个节点定义一个载重值$M_i$。则删除一个节点$j$后，会将$M_j-1$传递给父亲节点。如果父亲节点也被删除，则会将$M_i-1$传递给父亲的父亲。由此可以看出，删除的顺序不会影响父亲增加载重值的变化。
基于顺序不会受到影响的前提下，我们来思考第二个问题。若存在$a-b-c$这样的一棵树，其中a为根。现在存在两种方案，一种是删除$c$节点，一种是删除b节点，哪种更优？显然是删除c更优。因为删除b会导致根节点载重量变大的同时，还使得b节点无法充分利用。即损耗了a的载重，又没有充分利用b的载重量。而删除c节点后，a还能够有剩余的载重量，整体处于最优状态。由此，得出第二个结论，删除儿子节点比删除父亲节点优。
最后，如果有多个儿子可以删除，你会如何选择？必定是选取产生代价小的儿子删除。
得到如上三点后，其实做法就很显然了：自底向上，能删就删。
CODE
CODE - Click Here