题目大意：
给你一棵树，你可以删掉一些边，使得分除去的子树中至少有一棵大小为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，我们要将其与主树连接的边算入答案。
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int N=;
struct Edge {
int to,id;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &i) {
e[u].push_back((Edge){v,i});
e[v].push_back((Edge){u,i});
}
int size[N],f[N][N];
int t[N],pre[N];
std::vector<int> v[N][N];
void dfs(const int &x,const int &par) {
size[x]=;
int eid;
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
if(y==par) {
eid=e[x][i].id;
continue;
}
pre[y]=e[x][i].id;
dfs(y,x);
size[x]+=size[y];
}
f[x][]=;
f[x][size[x]]=;
v[x][size[x]].push_back(eid);
std::fill(&f[x][],&f[x][size[x]],inf);
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
eid=e[x][i].id;
if(y==par) continue;
memcpy(t,f[x],sizeof t);
for(int j=;j<=size[y];j++) {
for(int k=;k<size[x]-j;k++) {
if(f[x][k]==inf) continue;
if(f[x][k]+f[y][j]<t[k+j]) {
t[k+j]=f[x][k]+f[y][j];
v[x][k+j]=v[x][k];
v[x][k+j].insert(v[x][k+j].end(),v[y][j].begin(),v[y][j].end());
}
}
}
memcpy(f[x],t,sizeof t);
}
}
int main() {
int n=getint(),k=getint();
for(register int i=;i<n;i++) {
add_edge(getint(),getint(),i);
}
dfs(,);
int ans=f[][size[]-k],node=;
for(register int root=;root<=n;root++) {
if(size[root]<k) continue;
f[root][size[root]-k]++;
v[root][size[root]-k].push_back(pre[root]);
if(f[root][size[root]-k]<ans) {
ans=f[root][size[root]-k];
node=root;
}
}
printf("%d\n",ans);
for(register unsigned i=;i<v[node][size[node]-k].size();i++) {
printf("%d ",v[node][size[node]-k][i]);
}
return ;
}