树形DP，一棵树有N个结点，给出一个P，要求切断最少的边使树的规模达到P。
这题我是参考的别人的代码，状态转移方程最初很难理解，后来明白了，它扫描时，默认父结点是光杆司令一个，随着扫描子树才把子树连到父结点上。
1 #include <stdio.h> 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 }