题意是给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为m个的
设f[i][j]表示i号点所在的子树中选了j个点至少需要删去f[i][j]条边。
code：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 155 7 #define inf 1061109567 8 using namespace std; 9 char ch; 10 int n,k,a,b,tot,ans,now[maxn],son[maxn<<1],pre[maxn<<1]; 11 int siz[maxn],deg[maxn],f[maxn][maxn],tmp[maxn]; 12 bool ok; 13 void read(int &x){ 14 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 15 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 16 if (ok) x=-x; 17 } 18 void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;} 19 void dfs(int u,int fa){ 20 f[u][1]=0,siz[u]=1; 21 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) 22 if (v!=fa){ 23 dfs(v,u); 24 memset(tmp,63,sizeof(tmp)); 25 for (int i=1;i<=siz[u];i++) tmp[i]=f[u][i]+1; 26 for (int i=1;i<=siz[u];i++) 27 for (int j=1;j<=siz[v];j++) tmp[i+j]=min(tmp[i+j],f[u][i]+f[v][j]); 28 siz[u]+=siz[v]; 29 for (int i=1;i<=siz[u];i++) f[u][i]=tmp[i]; 30 } 31 } 32 int main(){ 33 read(n),read(k); 34 for (int i=1;i<n;i++) read(a),read(b),put(a,b),put(b,a); 35 memset(f,63,sizeof(f)); 36 dfs(1,0); 37 ans=f[1][k]; 38 for (int i=2;i<=n;i++) ans=min(ans,f[i][k]+1); 39 printf("%d ",ans); 40 return 0; 41 }