题目描述

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

戳

Solve

树形DP……
首先让我们设计一下状态。
那就直接点，设f[u][j]为以u为根节点的子树，保留j个节点（包括ta本身），所用最小的道路数。
初始：所有的状态都赋个极大值，然后赋f[u][1]都为子节点数目，因为ta要只剩下自己。
目标：min（f[root][p],f[u][p]+1($p!=root$) ) root为整棵树的根节点。
+1是因为要从u的父节点除去到u的边。
转移方程：f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-1),用v来更新u，所以需要保留u到v这条边，所以+1

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000
using namespace std;
int n,p,root,ans=10000000;
int f[N][N],du[N],cnt[N];
int head[N],len,to[N],nxt[N];
int u,v;
bool vis[N];
void add(int u,int v){
	to[++len]=v;
	nxt[len]=head[u];
	head[u]=len;
}
void dfs(int u){
	cnt[u]=1;
	f[u][1]=min(f[u][1],du[u]);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		dfs(v);
		cnt[u]+=cnt[v];
		for(int j=cnt[u];j>=1;j--){
			for(int k=1;k<j;k++) f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-1);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		du[u]++;vis[v]=true;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			root=i;
			break;
		}
	}
	dfs(root);
	ans=f[root][p];
	for(int i=1;i<=n;i++) ans=min(ans,f[i][p]+1);
	printf("%d",ans);
	return 0;
}