树形背包（有依赖性的背包） 由底向上更新，把子树处理成一个最优物品集，即像背包九讲说的一样，对于所以费用相等的，我们用01背包跑一个最大的价值，作为一个新的物品集。而向上更新时，每一个容量对于每一个物品集的选取而言，相当于做一次多重背包，选择一个取法，作为最优解，而这些容量对应的最优解集又会作为一个新的最优物品集回溯上去。
AC代码
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=205; const int inf=0x3f3f3f3f; const int mod=1e7+7; const LL maxn=1e18; #define fi first #define se second #define ls (i<<1) #define rs ((i<<1)|1) LL read() { LL x=0,t=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); } while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } /// f[u][j]=max(f[v][j-k-1]+f[v][k]+w[u][v],f[u][j]); struct edge { int from,to,w,next; edge(){} edge(int ff,int tt,int ww,int nn) { from=ff; to=tt; w=ww; next=nn; } }; edge e[N<<1]; int n,m,tot; int head[N],f[N][N],num[N]; void add(int from,int to,int w) { e[++tot]=edge(from,to,w,head[from]); head[from]=tot; } void dfs(int u,int pre) { num[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==pre) continue; dfs(v,u); num[u]+=num[v]; } for(int i=head[u];i;i=e[i].next) { int v=e[i].to,w=e[i].w; if(v==pre) continue; for(int j=min(m,num[u]);j>=0;j--) ///能保留的最多边（两个取min 是为了优化常数，并不是必要的） for(int k=min(j-1,num[v]);k>=0;k--) /// j-k -1 是因为取了他的子树的边必须要取他与子树根结点的连边 f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w); } } int main() { n=read(); m=read(); for(int i=1;i<n;i++) { int x=read(),y=read(),z=read(); add(x,y,z); add(y,x,z); } dfs(1,0); printf("%d\n",f[1][m] ); return 0; }