https://www.luogu.org/problemnew/show/P1272

一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。

输入输出格式

输入格式：

 

第1行：2个整数，N和P

第2..N行：每行2个整数I和J，表示节点I是节点J的父节点。

 

输出格式：

 

单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。

 

题意：删除最少的边，使得树中出现一个大小为p的连通块。

思路：设f(u,i):只考虑以u为根的子树，分离出大小为i的连通块需要删除的最少边数。

f(u,1)=u的儿子数

f(u,i)通过枚举子结点，借助泛化背包的思想进行树上背包转移（其实就是枚举每一个儿子，依次加入一个泛化背包，依次两两合并）

以下节选自《背包九讲》：

  

下面是样例的树：

#include<bits/stdc++.h>
using namespace std;
#define maxn 200

int n,p,f[maxn][maxn],fa_num[maxn],root;
vector<int> child[maxn];

void dfs(int u)
{	
	f[u][1]=child[u].size();
	for(int i=0;i<child[u].size();i++)
	{
		int v=child[u][i];
		dfs(v);
		for(int j=p;j>=2;j--)	//这行压了维，必须逆序 
		{
			for(int k=1;k<j;k++)
				f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-1);
		}
	}
}
	
int ans()
{
	int ret=f[root][p];
	for(int i=1;i<=n;i++)if(i!=root)ret=min(ret,f[i][p]+1);
	return ret;
}

int main()
{
//	freopen("input.in","r",stdin);
	int x,y; 
	cin>>n>>p;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		child[x].push_back(y);
		fa_num[y]++;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)if(!fa_num[i])root=i;
	dfs(root);	
	cout<<ans()<<endl;
	return 0;
}