poj 1947 经典树形dp

经典树形dp：问在一棵树上最少删除多少条边可以分离出一个节点数为p的子树。

定义状态：

　　dp[i][j]表示从i为根的子树上分离出一个节点数为j的子树的代价（最少需要删除的边数）。

　　考虑i节点的每个儿子ii，ii可以选或者不选（切断），然后就转化成了背包问题。

　　dp[u][j] = min( dp[u][j], dp[u][j - k] + dp[v][k] );

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int INF = 9999999;
 7 const int N = 151;
 8 int dp[N][N];
 9 int head[N];
10 int f[N];
11 int n, p, e;
12 
13 void init()
14 {
15     e = 0;
16     memset( f, -1, sizeof(f) );
17     memset( head, -1, sizeof(head) );
18 }
19 
20 struct Edge
21 {
22     int v, next;
23 } edge[N];
24 
25 void addEdge( int u, int v )
26 {
27     edge[e].v = v;
28     edge[e].next = head[u];
29     head[u] = e++;
30 }
31 
32 void dfs( int u )
33 {
34     dp[u][1] = 0;
35     for ( int i = 2; i <= p; i++ )
36     {
37         dp[u][i] = INF;
38     }
39     for ( int i = head[u]; i != -1; i = edge[i].next )
40     {
41         int v = edge[i].v;
42         dfs(v);
43         for ( int j = p; j >= 1; j-- )
44         {
45             dp[u][j]++;
46             for ( int k = 1; k <= j - 1; k++ )
47             {
48                 dp[u][j] = min( dp[u][j], dp[u][j - k] + dp[v][k] );
49             }
50         }
51     }
52 }
53 
54 int main ()
55 {
56     while ( scanf("%d%d", &n, &p) != EOF )
57     {
58         init();
59         for ( int i = 1; i < n; i++ )
60         {
61             int u, v;
62             scanf("%d%d", &u, &v);
63             addEdge( u, v );
64             f[v] = u;
65         }
66         int root;
67         for ( root = 1; f[root] != -1; root = f[root] ) ;
68         dfs(root);
69         int ans = dp[root][p];
70         for ( int i = 1; i <= n; i++ )
71         {
72             if ( i == root ) continue;
73             ans = min( ans, dp[i][p] + 1 );
74         }
75         printf("%d
", ans);
76     }
77     return 0;
78 }