f[ i ][ j ] 表示 i 为根节点选择 j 个点要去掉的最小边数。
一开始初始化所有边都去掉，只剩下本身一个点，值等于度数，根据是否为根结点加减一。
然后dp时-1是应为要加上 u 到 v 的一条边，dp表示要去掉的边，则要去掉的一条边则减一
代码语言：javascript复制//洛谷P1272 重建道路
//树形dp
#include <bits/stdc .h>
using namespace std;
const int maxn = 155;
struct N{
int nxt,v;
}ed[maxn<<2];
int dp[maxn][maxn],du[maxn];
int head[maxn],cnt,n,p,ans=0x7ffffff;
void add(int u,int v){
cnt ;
ed[cnt].v = v;
ed[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u,int fa){
dp[u][1] = du[u] - (fa!=0);//u为根节点选择i个点要去掉的最小边数
for(int v,i=head[u];i;i=ed[i].nxt){
v = ed[i].v;
if(v==fa)continue;
dfs(v,u);
for(int j=p;j>=1;j--){
for(int k=1;k<j;k ){
dp[u][j] = min(dp[u][j],dp[u][k] dp[v][j-k]-1);
//一开始把所有边都删了，连接v u 还需要加上一条边
//所以去掉的边就少一条
}
}
}
ans = min(ans,dp[u][p] (fa!=0)); //不是根结点 还要去掉父结点和自己的连线
}
int main()
{
scanf("%d %d",&n,&p);
for(int i=1;i<n;i ){
int u,v;
scanf("%d %d",&u,&v);
du[u] ; du[v] ;
add(u,v); add(v,u);
}
memset(dp,0x3f,sizeof(dp));
dfs(1,0);
printf("%d",ans);
return 0;
}
