用了三维DP。
DP[s][m][p]表示对结点s和s的前m棵子树切割成一颗结点数为p且以s为根的子树所需的最少切割数。
则根据第m棵子树是否被切割得到状态转移方程：
dp[s][m][p]=min{dp[s][m-1][p]+1,min{dp[s][m-1][p-k]+dp[son(s,m)][all(s,m)][k]}}
其中all(s,m)表示s的第m棵子结点所含儿子的个数。
自底向上求解的时候，用一个队列存储当前儿子结点个数为0的结点，每从队列中取出一个结点，则将该结点的父节点儿子数减1。这样就避免了记忆化DP所消耗的递归空间。
废话不说，贴AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int dp[151][151][151],fa[151],sonnum[151],sn[151];
queue<int> qs;
vector<int> link[151];

int main(){
	//freopen("in.txt","r",stdin);
	
	int N,P,i,j,k,f,s,si,tmp,r;
	while(scanf("%d %d",&N,&P)!=EOF){
		memset(dp,0xff,sizeof(dp));
		memset(fa,0,sizeof(fa));
		memset(sonnum,0,sizeof(sonnum));
		while(!qs.empty())qs.pop();
		for(i=1;i<=N;i++)link[i].clear();
		for(i=1;i<N;i++){
			scanf("%d %d",&f,&s);
			link[f].push_back(s);
			sonnum[f]++;
			fa[s]=f;
		}
		for(i=1;i<=N;i++){
			if(sonnum[i]==0)qs.push(i);
			sn[i]=sonnum[i];
		}
		while(!qs.empty()){
			s=qs.front();qs.pop();
			r=s;
			if((--sonnum[fa[s]])==0)qs.push(fa[s]);
			dp[s][0][1]=0;
			for(i=1;i<=sn[s];i++){
				si=link[s][i-1];
				for(j=1;j<=P;j++){
					if(dp[s][i-1][j]!=-1)dp[s][i][j]=dp[s][i-1][j]+1;
					else dp[s][i][j]=-1;
					for(k=1;k<j;k++){
						if(dp[s][i-1][j-k]!=-1 && dp[si][sn[si]][k]!=-1){
							tmp=dp[s][i-1][j-k] + dp[si][sn[si]][k];
							if(dp[s][i][j]==-1 || dp[s][i][j]>tmp)dp[s][i][j]=tmp;
						}
					}
				}
			}
		}
		for(tmp=dp[r][sn[r]][P],i=1;i<=N;i++){
			if(dp[i][sn[i]][P]!=-1 && tmp>(dp[i][sn[i]][P]+1))tmp=dp[i][sn[i]][P]+1;
		}
		printf("%d\n",tmp);
	}
	
	return 0;
}