一场可怕的地震后，人们用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个节点的子树的道路的最小数目。
输入样例#1： 复制
11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11输出样例#1： 复制
2【样例解释】
如果道路1-4和1-5被破坏，含有节点（1，2，3，6，7，8）的子树将被分离出来
我们设dp[k][i][j]表示以i为根的子树，在前k个儿子中，分离出一个大小为j的子树（必须包含i），所需要最少的操作次数。
那么我们每计算到第k+1个新的儿子v时(full_son[v]表示v的儿子个数)，
dp[k+1][i][j]=min(dp[k][i][j-t]+dp[full_son[v]][v][t]);
由于一个树形关系，我们需要在一个dfs上进行dp，即先dfs(v),然后更新dp[k+1][i][j]。
这个k的一维显然可以用滚动数组优化掉。
那么就是
j=m->1 t=1->j dp[i][j]=min(dp[i][j-t]+dp[v][t]);
同时，dp一律要注意初始化，即刚开始时所有的dp[i][1]=du[i]（du[i]表示与i连边的节点数，又称i的入度（树是无向边哟！））
#include<bits/stdc++.h> #define f(i,l,r) for(i=(l);i<=(r);i++) #define ff(i,r,l) for(i=(r);i>=(l);i--) using namespace std; const int MAXN=155,INF=10000000; int n,P; struct Edge{ int v,w,nxt; }e[MAXN<<1]; int h[MAXN],tot; int deg[MAXN]; int dp[MAXN][MAXN],ans=INF; inline void add(int u,int v) { e[tot].v=v; e[tot].nxt=h[u]; h[u]=tot++; } inline void dfs(int u,int fa) { int i,j,k; dp[u][1]=deg[u]; for(i=h[u];~i;i=e[i].nxt){ int v=e[i].v; if(v==fa) continue; dfs(v,u); ff(j,P,2){ f(k,1,j-1){ dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2); } } } ans=min(ans,dp[u][P]); } int main() { ios::sync_with_stdio(false); memset(h,-1,sizeof(h)); memset(dp,60,sizeof(dp)); int i,j,u,v; cin>>n>>P; f(i,1,n-1){ cin>>u>>v; add(u,v); add(v,u); deg[u]++; deg[v]++; } dfs(1,0); cout<<ans<<endl; return 0; }
