树形DP，一棵树有N个结点，给出一个P，要求切断最少的边使树的规模达到P。

这题我是参考的别人的代码，状态转移方程最初很难理解，后来明白了，它扫描时，默认父结点是光杆司令一个，随着扫描子树才把子树连到父结点上。

1 #include 
     
       2 #define N 152 3 int fst[N],nxt[N],notrt[N]; 4 int dp[N][N],n,p; 5 void dfs(int u) 6 { 7     int i,j,v,t; 8     for(i = 0; i <= p; i++) dp[u][i]=N; 9     dp[u][1] = 0;10     for(v = fst[u]; v; v = nxt[v])11     {12         dfs(v);13         for(i = p; i >= 0; i--)14         {15             t = dp[u][i]+1;16             for(j = 0; j <= i; j++)17             if(dp[u][i-j] + dp[v][j] < t)18                 t = dp[u][i-j] + dp[v][j];19             dp[u][i] = t;20             //printf("dp[%d][%d]:%d\n",u,i,t);21         }22     }23 }24 int main()25 {26     int i,a,b,ans;27     scanf("%d%d",&n,&p);28     for(i = 1; i < n; i++)29     {30         scanf("%d%d",&a,&b);31         nxt[b] = fst[a];32         fst[a] = b;33         notrt[b] = 1;34     }35     for(i = 1; notrt[i]; i++);36     dfs(i);37     ans = dp[i][p];38     for(i = 1; i <= n; i++)39         if(dp[i][p] < ans)40             ans = dp[i][p]+1;41     printf("%d\n",ans);42     return 0;43 }