poj 1947 Rebuilding Roads
题意:用最少的切割次数,分割出一个节点数为p的子树
由于我们不知道最后得到的是哪个子树,所有可以全部求出来,最后枚举每个点,以该点作为根的子树下有p个节点的切割次数是多少
定义:dp[u][m]:表示以u为根的子树下有m个节点的最小切割次数,注意这里,u和它的父亲fa的连边是没有切断的,但是我们并不考虑它的fa分支,只看u这个子树,所以最后要使的u这个子树完全独立出来,还要切割多一次,切断u和fa的连线
最终的答案是
ans = dp[1][p];以1为根的子树下有p个节点的最少切割次数,由于1没有fa,所以不用加1
ans = min{ dp[u][p] } +