题目链接：https://www.luogu.com.cn/problem/P2015
树上的0-1背包问题。
因为这是一棵树，所以当某条边被保留下来时，从根节点到这条边的路径上的所有边也都必须保留下来。
设dp[u][j]表示以u为根的子树中，选取j条边的最大值。
那么转移方程为：$dp[u][j]=max(dp[u][j],dp[u][j-1-k]+dp[v][k]+edge[i].val)$
u为当前节点，v是u的一个子节点，sum[u]表示u的子树上的边数，m为最多保留边数。
注意一些边界：
如为何是dp[u][j-1-k]而不是dp[u][j-k]或者为何k的取值范围要小于等于j-1而不是j：
因为这个子树与u之间有一条边，即u与v之间有一条边，需要-1。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=200; 6 struct node{ 7 int to,next,val; 8 }edge[N<<1]; 9 int head[N],tot; 10 int sum[N],dp[N][N],n,m; 11 void add(int u,int v,int w){ 12 edge[tot].to=v; 13 edge[tot].next=head[u]; 14 edge[tot].val=w; 15 head[u]=tot++; 16 } 17 void DFS(int u,int fa){ 18 for(int i=head[u];i!=-1;i=edge[i].next){ 19 int v=edge[i].to; 20 if(v==fa) continue; 21 DFS(v,u); 22 sum[u]+=sum[v]+1;//子树边数 23 for(int j=min(m,sum[u]);j>=1;j--){//注意边界 24 for(int k=min(j-1,sum[v]);k>=0;k--){//注意边界 25 dp[u][j]=max(dp[u][j],dp[u][j-1-k]+dp[v][k]+edge[i].val); 26 } 27 } 28 } 29 } 30 int main(){ 31 memset(head,-1,sizeof(head)); 32 scanf("%d%d",&n,&m); 33 for(int i=1;i<n;i++){ 34 int u,v,w; 35 scanf("%d%d%d",&u,&v,&w); 36 add(u,v,w); add(v,u,w); 37 } 38 DFS(1,-1); 39 printf("%d\n",dp[1][m]); 40 return 0; 41 }