树形DP#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
int indg[
152],n,p,cnt,f[
152][
152],head[
152],nex[
302],to[
302];
void inline read(
int &
x){
char ch=getchar();x=
0;
while(!isdigit(ch))ch=
getchar();
while(isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=
getchar();}
}
void addedge(
int u,
int v){
to[++cnt]=v;nex[cnt]=head[u];head[u]=
cnt;
}
void dfs(
int now,
int fa){
f[now][1]=
indg[now];
for(
int i=head[now];i;i=
nex[i]){
int v=
to[i];
if(v==fa)
continue;
dfs(v,now);
for(
int j=p;j>
0;j--
)
for(
int k=
1;k<j;k++
)
f[now][j]=min(f[now][j],f[now][k]+f[v][j-k]-
2);
//注意：这里是-2，因为在dfs(v)时在已经把所有与u和edge[i].to相连接的节点给砍掉了，但是u和edge[i].to相连的的度应该保留，而这段相连的度，在u中加了一次，在to中也加了一次，所以应该-2
}
}
int main(){
read(n);read(p);
memset(f,0x3f,
sizeof(f));
for(
int i=
1;i<n;i++
){
int u,v;read(u);read(v);
indg[u]++;indg[v]++
;
addedge(u,v);addedge(v,u);
}
dfs(1,
0);
int ans=
1e9;
for(
int i=
1;i<=n;i++)ans=
min(ans,f[i][p]);
printf("%d",ans);
}
转载于:https://www.cnblogs.com/MikuKnight/p/9016461.html
相关资源：JAVA上百实例源码以及开源项目
