思考过程
一眼树状dp+背包dp
每一根树枝占用 1 空间 带来的价值由题目输入
设计 f[u][i] 表示在考虑以 u 为根的子树时 分配给它 i 根树枝 所能达到的最大价值
于是在以 u 为根的子树中想要新拓展一个以 v 为根的子树时
有转移方程 f[u][i]=max(f[u][i],f[u][i-k-1]+f[v][k]+w)
——由 u 至 v ，总共空间为 i ，分给以 v 为根的子树空间为 k
是否选择加入以 v 为根的子树 为 01 背包 注意倒序循环
这里的 i-k-1 是因为由 u 至 v 本身就需要连接一条边
初版代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 115
#define il inline
#define Inf 0x3f3f3f3f
int n,m;
int x,y,z;
int sz[N];
int f[N][N];
struct node{
int to,next,w;
}tr[N<<1];
int cnt,head[N];
il int read()
{
int x=0;
bool f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=0;
for(;isdigit(ch);ch=getchar())
x=(x<<1)+(x<<3)+ch-'0';
return f?x:(~(x-1));
}
void add(int u,int v,int w)
{
tr[++cnt].to=v;
tr[cnt].w=w;
tr[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)
{
for(int i=head[u];i!=-1;i=tr[i].next)
{
int v=tr[i].to;
if(v==fa)continue;
// cout<<u<<"->"<<v<<endl;
dfs(v,u);
for(int j=m;j>=1;j--)
{
for(int k=j-1;k>=0;k--)
{
f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+tr[i].w);
}
}
}
}
int main()
{
n=read();m=read();
for(int i=0;i<=n;i++)head[i]=-1;
for(int i=1;i<n;i++)
{
x=read();y=read();z=read();
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
cout<<f[1][m];
}
一些似乎有用的小优化
对着转移过程仔细思考一下
for(int j=m;j>=1;j--)
{
for(int k=j-1;k>=0;k--)
{
f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+tr[i].w);
}
}
这里的 j 是为以 u 为根的子树留出的空间
而 k 是为以 v 为根的子树留出的空间
那么有没有一种可能 这些子树根本没有那么多树枝来占用空间呢
于是可以在 dfs 的过程中统计子树中的树枝数量
在 dp转移 过程中就可以减小一些时间复杂度了（也许微不足道？）
最终代码（节选 dfs 部分）
点我查看代码喔~
void dfs(int u,int fa)
{
for(int i=head[u];i!=-1;i=tr[i].next)
{
int v=tr[i].to;
if(v==fa)continue;
// cout<<u<<"->"<<v<<endl;
dfs(v,u);
sz[u]+=sz[v]+1;//在这里统计了树枝数量
for(int j=min(m,sz[u]);j>=1;j--)
{
for(int k=min(sz[v],j-1);k>=0;k--)
{
f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+tr[i].w);
}
}
}
}