思路:dp[i][j]表示,以i节点为根,删去j个节点最少要断几条边。
那么dp[u][j]=min(dp[u][j],dp[v][k]+dp[u][j-k]);//选取最优状态
dp[u][j]=min(dp[u][j],dp[u][j-son[v]]+1);//切断与子节点相连的边
对于子节点
dp[v][n-son[v]]=1;
dp[v][j]=min(dp[v][j],dp[v][j-n+son[v]]+1)//表示不需要由父节点过来的那条分支
最有从所有状态中选举最优的dp[i][n-p];
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Maxn 160
#define Maxm 200010
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 0x7fffffff
#define Mod 1000000007
using namespace std;
int head[Maxn],vi[Maxn],e,dp[][],n,p,son[],root[Maxn];
struct Edge{
int u,v,next;
}edge[Maxm];
void init()
{
memset(head,-,sizeof(head));
memset(vi,,sizeof(vi));
memset(son,,sizeof(son));
for(int i=;i<=;i++){
root[i]=i;
for(int j=;j<=;j++){
dp[i][j]=;
}
dp[i][]=;
}
e=;
}
void add(int u,int v)
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
edge[e].u=v,edge[e].v=u,edge[e].next=head[v],head[v]=e++;
}
void dfs(int u)
{
int i,v,j,k;
vi[u]=;
son[u]=;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(vi[v]) continue;
dfs(v);
son[u]+=son[v];
for(j=n-;j>=;j--){
for(k=;k<=j;k++){
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
}
if(j>=son[v])
dp[u][j]=min(dp[u][j],dp[u][j-son[v]]+);
}
dp[v][n-son[v]]=;
for(j=n-;j>=n-son[v];j--)
dp[v][j]=min(dp[v][j],dp[v][j-n+son[v]]+);
}
}
int main()
{
int i,j,u,v;
while(scanf("%d%d",&n,&p)!=EOF){
init();
for(i=;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
if(p==n){
printf("0\n");
continue;
}
if(p==n-)
{
printf("1\n");
continue;
}
dfs();
int ans=;
for(i=;i<=n;i++){
ans=min(ans,dp[i][n-p]);
}
printf("%d\n",ans);
}
return ;
}