题意：给出一个树形结构，求P个节点的子树最少要去掉几条边
分析：DP[root][j] 表示 以第 root 个为根节点， 包含j 个节点需要去掉几条边。那么对于 root 这个根节点来说， 要么选择 他的一个 儿子 k, 要么不选择， 如果选择 dp[root][j] = min( dp[k][i] + dp[root][j - i] ), k为root的子节点， 其中 0 < i < j； 如果不选择的话，就去掉root 和 k之间连线，dp[root][j] = dp[root] [j] + 1;
1 #include <iostream>View Code
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <cstdio>
6 using namespace std;
7 const int Max = 200;
8 const int INF = 0x3f3f3f3f;
9 vector<int> son[Max];
10 int n, p;
11 int indegree[Max];
12 int dp[Max][Max];
13 void dfs(int root)
14 {
15 int Size = son[root].size();
16 for (int i = 0; i <= p; i++)
17 dp[root][i] = INF;
18 dp[root][1] = 0; //全都设为0，对于叶子节点来说就是0
19 for (int i = 0; i < Size; i++)
20 {
21 int u = son[root][i];
22 dfs(u);
23 int temp;
24 for (int j = p; j >= 1; j--)
25 {
26 temp = dp[root][j] + 1; // 不选择u这个子节点，那么就+1
27 for (int k = 1; k < j; k++) // 枚举root的节点个数，所以第一层 i 要从p开始枚举，因为这里要用到 小的，保证小的是上一个状态
28 {
29 temp = min(temp, dp[root][k] + dp[u][j - k]);
30 }
31 dp[root][j] = temp;
32 }
33 }
34 }
35
36 int solve(int root)
37 {
38 dfs(root);
39 int ans = dp[root][p]; // 这个子树可能以root为根
40 for (int i = 1; i <= n; i++) // 也可以不以root为根
41 ans = min(ans, dp[i][p] + 1);
42 return ans;
43
44 }
45 int main()
46 {
47 while (scanf("%d%d", &n, &p) != EOF)
48 {
49 for (int i = 0; i <= n; i++)
50 son[i].clear();
51 memset(indegree, 0, sizeof(indegree));
52 int I, J, root;
53 for (int i = 1; i < n; i++)
54 {
55 scanf("%d%d", &I, &J);
56 son[I].push_back(J);
57 indegree[J]++;
58 }
59 for (int i = 1; i <= n; i++)
60 {
61 if (!indegree[i]) // 找根节点
62 {
63 root = i;
64 break;
65 }
66 }
67
68 printf("%d\n", solve(root));
69 }
70 return 0;
71 }