/*
最少地删去树中边，使分离出M个点
题意理解一：M个点可以为森林
f[i][j]表示以i为根的子树，分离出去j个点，最少删边数
题意理解二：M个点必须为一个棵树
f[i][j]表示以i为根的子树，保留j个点，最少删边数
初值纠结了，根源还是理解不深...
1.背包的含义
容易想到f[i][j] = min(f[p][k] + f[i][j - k])
相当于有容量为j的背包，在每个孩子结点中要选一个体积为k的物品放入，
分组背包，注意每个孩子结点中必须选且仅选一个物品放入
初值呢，
f[i][0]=0，表示不选就不用删边
f[i][1]=count(child[i])选一个，就只能是根，删去其他孩子结点
然后把j倒序地更新一遍，物品写在内层，就行了么？错！
注意啊，f[i][j]实际上还隐含着2维
f[i][p][k][j]表示以i为根的子树，在前p组中，第p组前k个物品中，填充容量j的最小花费
于是f[i][1]=count(child[i])表达的实际上是前所有组中，填充容量1的最小花费
这可不是初值！
好吧，我这里把孩子连向根的边算作子树的一部分，而不是根的。
于是f[i][1]=0，表示以i为根的子树，没开始放物品时，只有秃秃的根一个点，也就不存在什么边，所以也不需要删边。要说存在一条边，那就是这个根和他父亲结点的连边了。
所以f[i][0]=1，表示都也不取的话，就把与父亲相连的边也删掉
于是我写出下面这段转移
for j = M to 1
    t = 0;
    for k = 0 to j
	    if (f[i][j - t] + f[p][t] > f[i][j - k] + f[p][k]) t = k;
    f[i][j] = f[i][j - t] + f[p][t]
t的设置，使得每组必须选一个物品k
但上面的代码还是WA
2.不和谐的转移
k=j，在背包中看起来无伤大雅，但在树中
f[i][j-k] + f[p][k]，表示原树中什么都不取，j个点全让子树p来取
这与f[i][j]的定义相矛盾，f[i][j]中只要j>0，那根是一定要取的
所以，k < j
这样下来终于AC了~
最后注意下分离的树中不一定包含总根，也可以是棵子树，需要遍历下所有子树
*/
http://blog.csdn.net/cmonkey_cfj/article/details/7264580