题目大意：
给你一棵树，你可以删掉一些边，使得分除去的子树中至少有一棵大小为k。
问最少删去多少边，以及删边的具体方案。
思路：
树形DP。
f[i][j]表示以i为根，子树中去掉j个点最少要删边的数量；
v[i][j]表示其具体方案。
然后对每个点跑一下背包。
状态转移方程f[x][k+j]=min{f[x][k]+f[y][j]|y为x子结点}。
注意y的不同状态不能同时对x的同一个状态产生影响，所以转移的时候必须把数组复制一遍，将原数组和转移过后的数组隔离开来。
v的转移只需要把v[x][k]和v[y][j]并起来就OK了。
最后答案枚举每个结点的f[node][size[node]-k]，如果不是一开始假定的根结点1，我们要将其与主树连接的边算入答案。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int inf=0x7fffffff; 13 const int N=401; 14 struct Edge { 15 int to,id; 16 }; 17 std::vector<Edge> e[N]; 18 inline void add_edge(const int &u,const int &v,const int &i) { 19 e[u].push_back((Edge){v,i}); 20 e[v].push_back((Edge){u,i}); 21 } 22 int size[N],f[N][N]; 23 int t[N],pre[N]; 24 std::vector<int> v[N][N]; 25 void dfs(const int &x,const int &par) { 26 size[x]=1; 27 int eid; 28 for(unsigned i=0;i<e[x].size();i++) { 29 const int &y=e[x][i].to; 30 if(y==par) { 31 eid=e[x][i].id; 32 continue; 33 } 34 pre[y]=e[x][i].id; 35 dfs(y,x); 36 size[x]+=size[y]; 37 } 38 f[x][0]=0; 39 f[x][size[x]]=1; 40 v[x][size[x]].push_back(eid); 41 std::fill(&f[x][1],&f[x][size[x]],inf); 42 for(unsigned i=0;i<e[x].size();i++) { 43 const int &y=e[x][i].to; 44 eid=e[x][i].id; 45 if(y==par) continue; 46 memcpy(t,f[x],sizeof t); 47 for(int j=0;j<=size[y];j++) { 48 for(int k=0;k<size[x]-j;k++) { 49 if(f[x][k]==inf) continue; 50 if(f[x][k]+f[y][j]<t[k+j]) { 51 t[k+j]=f[x][k]+f[y][j]; 52 v[x][k+j]=v[x][k]; 53 v[x][k+j].insert(v[x][k+j].end(),v[y][j].begin(),v[y][j].end()); 54 } 55 } 56 } 57 memcpy(f[x],t,sizeof t); 58 } 59 } 60 int main() { 61 int n=getint(),k=getint(); 62 for(register int i=1;i<n;i++) { 63 add_edge(getint(),getint(),i); 64 } 65 dfs(1,0); 66 int ans=f[1][size[1]-k],node=1; 67 for(register int root=2;root<=n;root++) { 68 if(size[root]<k) continue; 69 f[root][size[root]-k]++; 70 v[root][size[root]-k].push_back(pre[root]); 71 if(f[root][size[root]-k]<ans) { 72 ans=f[root][size[root]-k]; 73 node=root; 74 } 75 } 76 printf("%d ",ans); 77 for(register unsigned i=0;i<v[node][size[node]-k].size();i++) { 78 printf("%d ",v[node][size[node]-k][i]); 79 } 80 return 0; 81 }