题意是给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为m个的
设f[i][j]表示i号点所在的子树中选了j个点至少需要删去f[i][j]条边。
code：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 155
#define inf 1061109567
using namespace std;
char ch;
int n,k,a,b,tot,ans,now[maxn],son[maxn<<],pre[maxn<<];
int siz[maxn],deg[maxn],f[maxn][maxn],tmp[maxn];
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void dfs(int u,int fa){
f[u][]=,siz[u]=;
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if (v!=fa){
dfs(v,u);
memset(tmp,,sizeof(tmp));
for (int i=;i<=siz[u];i++) tmp[i]=f[u][i]+;
for (int i=;i<=siz[u];i++)
for (int j=;j<=siz[v];j++) tmp[i+j]=min(tmp[i+j],f[u][i]+f[v][j]);
siz[u]+=siz[v];
for (int i=;i<=siz[u];i++) f[u][i]=tmp[i];
}
}
int main(){
read(n),read(k);
for (int i=;i<n;i++) read(a),read(b),put(a,b),put(b,a);
memset(f,,sizeof(f));
dfs(,);
ans=f[][k];
for (int i=;i<=n;i++) ans=min(ans,f[i][k]+);
printf("%d\n",ans);
return ;
}