POJ 1947 Rebuilding Roads 树状dp+背包

Problem:
给一棵树，问最少砍多少刀就可以划分出来一个p个节点的子树。
Solution:
对于一个根节点i，我们定义这个i一定在最终划分出来的子树当中，dp[i][k]表示以i为根节点的子树划分出k个节点所需要的最少次数。那么dp[i][j+k] = min(dp[i][j+k], dp[i][j]+dp[son[i]][k]-1)。这个状态转换理解为：对于i为根节点的这颗子树，需要划分出来j+k个节点，那么我们可以从这个儿子中划分出来k个，从其它部分划分出来j个，-1是因为要把儿子那部分合并进来，就需要减一刀。最终动规完毕后，需要再遍历一遍所有节点，找到以哪个节点为根节点的子树才是最优解，而最后需要加上1，表示从原来的子树中分离出去。由于我们初始化ans的值为dp[root][p],所以我们也无需担心根节点这个答案+1后超出原来的值。有一些细节需要注意，具体看代码。
notes:
1. 没有处理0，而是放在最后处理，因为划分出来1个节点也是0刀，避免dp冲突，最后再遍历一遍即可。
2. dp[x][1]就代表其它兄弟节点不贡献值，所以也不用处理0这种情况。

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<vector>
#include<fstream>
#include<list>
#include<numeric>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s,0,sizeof(s))

const double PI = 3.141592653589;
const int INF = 0x3fffffff;

int dp[155][155];
int fa[155];
vector<int> Tree[155];
int n, p;

void solve(int x) {
for(int i = 0; i < Tree[x].size(); i++)
        solve(Tree[x][i]);
    dp[x][1] = Tree[x].size();
for(int i = 0; i < Tree[x].size(); i++) {
for(int j = p-1; j > 0; j--) {
if(dp[x][j] != INF) {
for(int k = 1; k <= p-j; k++) {
if(dp[Tree[x][i]][k] != INF)
                        dp[x][j+k] = min(dp[x][j+k], dp[Tree[x][i]][k]+dp[x][j]-1);
                }
            }
        }
    }
}

int main() {
// freopen("/Users/really/Documents/code/input","r",stdin);
// freopen("/Users/really/Documents/code/output","w",stdout);
        ios::sync_with_stdio(false);

int a, b, ans, root = 1;
    ms(fa);
for(int i = 0; i <= 150; i++)
for(int j = 0; j <= 150; j++)
            dp[i][j] = INF;

cin >> n >> p;
for(int i = 1; i < n; i++) {
cin >> a >> b;
        fa[b] = a;
        Tree[a].push_back(b);
    }
while(fa[root] != 0)
        root = fa[root];

    solve(root);

    ans = dp[root][p];
for(int i = 1; i <= n; i++)
if(dp[i][p] < ans)
            ans = dp[i][p]+1;

cout << ans << endl;

return 0;
}