题干：
The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.
Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.
Input
* Line 1: Two integers, N and P
* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J's parent in the tree of roads.
Output
A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.
Sample Input
11 61 21 31 41 52 62 72 84 94 104 11
Sample Output
2
Hint
[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]
题目大意：
将一棵n个节点的有根树，删掉一些边变成恰有m个节点的新树。求最少需要去掉几条边。
解题报告：
dp[i][j]代表，以 i 为根节点，砍掉 j 个子节点的子树，所要删除的边的个数
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pairusing namespace std;const int MAX = 555;const int INF = 0x3f3f3f3f;int dp[MAX][MAX];//以i节点为根节点，切掉了j个节点的最小刀数 int n,p;vector<int> vv[MAX];void dfs(int cur,int rt) {int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);for(int j = p; j>1; j--) {for(int k = 1 ; k < j ; ++k)//划分成子树下的节点和本身的节点数dp[cur][j] = min(dp[cur][j] , dp[v][k]+dp[cur][j-k]-2);}}}int main(){cin>>n>>p;for(int a,b,i = 1; i<=n-1; i++) {scanf("%d%d",&a,&b);vv[a].pb(b);vv[b].pb(a);}memset(dp,INF,sizeof dp);for(int i = 1; i<=n; i++) dp[i][1] = vv[i].size();dfs(1,-1);int ans = INF;for(int i=1;i<=n;i++) ans=min(dp[i][p],ans);cout <<ans <<endl;return 0 ;}
AC代码2：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int n,p,k,head[160],rd[160],dp[160][160],siz[160],ans=0x3f3f3f;struct edge {int to,next;} ed[330];void adde(int u,int v){ed[++k].to=v;ed[k].next=head[u];head[u]=k;}void dfs1(int u,int fa){siz[u]++;for(int i=head[u];i;i=ed[i].next){int v=ed[i].to;if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];}dp[u][siz[u]]=1;//如果切掉整棵子树，只需切掉与父节点的连边 dp[u][0]=0;//不切 }void dfs2(int u,int fa){for(int i=head[u];i;i=ed[i].next){int v=ed[i].to;if(v==fa) continue;dfs2(v,u);for(int j=siz[u]-1;j;j--)//我切多少 for(int k=0;k<=j;k++)//我的儿子切多少 dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);//我切j个节点切的最少边数=min 我切j-k个节点的最少边数+我的儿子切k个节点的最少边数 }if(siz[u]-p>=0)//有那么多节点 ans=min(ans,dp[u][siz[u]-p]+dp[u][siz[u]]);//min 切掉siz[u]-p个节点(剩P个节点)的最少边数+分开我与父亲的边 }int main(){scanf("%d%d",&n,&p);memset(dp,0x3f3f3f,sizeof(dp));//初始化为最大值 for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);adde(u,v);adde(v,u);}dfs1(1,1);//求siz数组 & 初始化 dp[1][siz[1]]=0;//根节点不需要与父节点分开 （没有父亲。。。） dfs2(1,1);//树形dp printf("%d",ans);return 0;}
