重建道路
一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。
显然是一道树形DP
然后看题解
树上分组背包问题
dp[u][i][j]表示以u为根的子树中，前i个子树中留下j个的最小花费
首先，dp[u][size[u]][1]=son_num[u]
以u为节点的子树留下1个节点的花费为u的子树个数
dp[u][i][j]=min(dp[u][i][j],dp[u][i-1][j-k]+dp[v][size[v]][k]-1);
i这一维可以滚动数组滚掉
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 155
int n,p,dp[N][N],out[N],in[N];
struct NODE{
int to,next;
} e[N];
int Head[N],num;
inline void add(int x,int y){
e[++num].to=y;
e[num].next=Head[x];
Head[x]=num;
}
inline int read(){
int x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
inline int min(int a,int b){
return a<b?a:b;
}
int dfs(int u){
dp[u][]=out[u];
int sum=;
for(int i=Head[u];i;i=e[i].next){
int v=e[i].to;
int sz=dfs(v); sum+=sz;
for(int j=sum;j>=;j--)
for(int k=;k<=min(sz,j);k++){
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-);
}
}
dp[u][sum]=;
return sum;
}
int main()
{
memset(dp,0x3f,sizeof(dp));
scanf("%d%d",&n,&p);
int x,y;
for(int i=;i<n;i++){
x=read(); y=read();
add(x,y);
out[x]++; in[y]++;
}
int st;
for(int i=;i<=n;i++)
if(!in[i]) {
st=i; break;
}
dfs(st);
int ans=0x7fffffff;
for(int i=;i<=n;i++)
ans=min(ans,dp[i][p]+(i==st?:));
printf("%d\n",ans);
return ;
}