【题意】：给出一颗有n个节点的树，问你最少切割多少条边可以得出一棵子树刚好包含p个节点。

【题解】：明显的树dp。
               做完这题突然发现我对树dp+背包的理解又加深了。
               设dp[u][i]表示以u为根的子树，得到包含i个节点的树的最少代价。
               dp[u][i] = min(dp[u][i] + 1, dp[u][i-j] + dp[v][j]),其中 1 <= j <= i，v 为 u 的儿子。
               枚举的时候注意要逆序，要不就开三维数组。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 155
19 const int inf = 1 << 25;
20 vector<int> vec[maxn];
21 int dp[maxn][maxn];
22 bool visit[maxn];
23 int n, p;
24 
25 void dfs(int u) {
26     int size = vec[u].size();
27     fill(&dp[u][0], &dp[u][maxn], inf);
28     dp[u][1] = 0;
29     for(int i = 0; i < size; i++) {
30         int v = vec[u][i];
31         dfs(v);
32         for(int j = p; j >= 1; j--) {
33             dp[u][j]++;
34             for(int k = 1; k < j; k++) {
35                 dp[u][j] = min(dp[u][j], dp[u][j-k] + dp[v][k]);
36             } 
37         }
38     }
39 }
40 
41 int main() {
42     int u, v, root;
43     while(~scanf("%d%d", &n, &p)) {
44         memset(visit, true, sizeof(visit));
45         for(int i = 0; i <= n; i++) vec[i].clear();
46         for(int i = 0; i < n - 1; i++) {
47             scanf("%d%d", &u, &v);
48             vec[u].pb(v);
49             visit[v] = false;
50         }
51         for(int i = 1; i <= n; i++)
52             if(visit[i]) root = i;
53         dfs(root);
54         int ans = dp[root][p];
55         for(int i = 1; i <= n; i++)
56             ans = min(ans, dp[i][p] + 1);
57         cout << ans << endl;
58     }
59     return 0;
60 }
61