dp[s][i]:记录s结点，要得到一棵i个节点的子树去掉的最少边数 考虑其儿子k 1）如果不去掉k子树，则 dp[s][i] = min(dp[s][j]+dp[k][i-j]) 0 <= j <= i
2）如果去掉k子树，则 dp[s][i] = dp[s][i]+1 总的为 dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) , dp[s][i]+1 )
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n,p,root; int dp[155][155],son[155],fa[155],bro[155]; void dfs(int root) { int tem,k; dp[root][1]=0; k=son[root]; while(k) { dfs(k); for(int i=p;i>=1;i--) { tem=dp[root][i]+1; for(int j=1;j<i;j++) { tem=min(tem,dp[k][j]+dp[root][i-j]); } dp[root][i]=tem; } k=bro[k]; } } int solve() { for(int i=1;i<=n;i++) { if(fa[i]==0){root=i;break;} } dfs(root); int ans=dp[root][p]; for(int i=1;i<=n;i++) { ans=min(ans,dp[i][p]+1); } return ans; } int main() { int a,b; scanf("%d%d",&n,&p); memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(bro,0,sizeof(bro)); memset(dp,10000,sizeof(dp)); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); bro[b]=son[a]; fa[b]=1; son[a]=b; } printf("%d",solve()); return 0; }
