一场可怕的地震后，人们用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个节点的子树的道路的最小数目。
11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11
2
【样例解释】
如果道路1-4和1-5被破坏，含有节点（1，2，3，6，7，8）的子树将被分离出来
树上背包dp
代码里有注释
#include<queue> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const ll inf = 1000000000000000000ll; const int maxn = 155; int dp[maxn][maxn]; // dp[i][j] 表示 在包含i的子树上 // 选取j个节点所需要删除的最小边数 int head[maxn*2],to[maxn*2],ne[maxn*2],tot=0; int du[maxn]; int n, p; int ans = 0x3f7f7f7f; inline void add(int u,int v){ to[tot] = v; ne[tot] = head[u]; head[u] = tot++; to[tot] = u; ne[tot] = head[v]; head[v] = tot++; } void dfs(int u,int fa){ dp[u][1] = du[u]-(fa != -1); // 这里是处理出 u 这个节点有多少个孩子 // 如果 fa == -1 那么 u 就是根节点 // 根节点的孩子数 为 其的度 // 如果 fa != -1 那么 u 就有父节点 // u 的孩子数等于 度-1 for(int i=head[u];i!=-1;i=ne[i]){ int v = to[i]; if(v==fa)continue; dfs(v,u); for(int j=p;j>=1;j--) for(int k=1;k<j;k++) dp[u][j] = min(dp[u][j],dp[u][j-k]+dp[v][k]-1); // 这里减1 是因为在dfs的第一条语句就把 (u,v)这条边删掉了 // 而 dp[v] 向 dp[u] 转移是不删这条边的 // 删边删多了 -1 之后才是正确的删边数 } ans = min(ans,dp[u][p]+(fa!=-1)); // 这里是判断有没有父节点 // 有的话还要删除和父节点之间的边 } int main(){ int u, v; scanf("%d%d",&n,&p); memset(head,-1,sizeof(head)); memset(dp,0x3f,sizeof(dp)); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); ++du[u];++du[v]; } dfs(1,-1); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/kongbb/p/11366242.html
