poj 1947 Rebuilding Roads | G-rated

poj 1947 Rebuilding Roads | G-rated

题意：用最少的切割次数，分割出一个节点数为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] } + 1 ; 以其他点为根的子树下有p个节点的最少切割次数，但是其他节点u都有fa，所以还要切掉u和fa的边

dp的转移：我们先来考虑这个问题。u为根的子树有m个节点，u有儿子v1，v2，v3,…….假设v1子树有k1个节点，v2子树有k2的节点，v3子树有k3个节点………….这其实就是一个组合起来的结果
dp[u][m] = dp[v1][k1] + dp[v2][k2] + dp[v3][k3] + dp[v4][k4]………………….
但每个子树下面保留多少个节点，是不确定的，可以1个，0个，多个。这其实就转化为了背包
总容量为m，每个子树下应该选进去多少个点ki，使得不超过容量m，价值最小

转移方程为
dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] – 1);
有时候写dp[u][j]会不好理解，实际上是dp[u][c][j]的，只不过和背包一样，进行了空间的优化，降维
dp[u][c][j]表示以u为根的子树，在考虑第前c个儿子子树后，包含了j个节点的最少切割次数，这和dp[u][j]是一样的

dp[u][1] = son; 以u为根的子树只保留一个节点u，那么说明其儿子都切断了，有多少个儿子子树只需要切多少刀，因而切son次

关于转移方程 dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] – 1);
dp[u][j-k] + dp[v][k] – 1 , dp[u][j-k]表示前c个儿子一共贡献了j-k个节点给u这个子树，dp[v][k]表示第c+1个儿子贡献了k个节点给u，为何要减1，因为对于u而言，相当于v子树拼接到u上次，要抵消掉之前切去的那条u—v的边

Read full article from poj 1947 Rebuilding Roads | G-rated