树形dp之强行二叉树（树上背包）（模板）

题目： 二叉苹果树

f[x][j]表示以x为根的树保留j条边（除x外j个结点）得到的最多苹果数
f[x][j]=max(f[x][i],f[x][k]+f[u][j-k-1]+w;
u是x的儿子

此题是树上背包（多叉树），树上背包可以看成二叉树的合并，
将左边的森林（可以为空）看成左子树，将右边依次枚举的单边看成右子树
其过程看成左子树不停向右拓展即合并右子树

#include<bits/stdc++.h>
using namespace std;
int const INF=0x3f3f3f3f;
int const N=1e2+7;
int n,cnt;
int head[N];
struct node{
    int a,next,len;
}edge[N<<1];
void add(int x,int y,int len){
    edge[++cnt].a =y;
    edge[cnt].len =len;
    edge[cnt].next =head[x];
    head[x]=cnt;
}
int const Q=1e2+7;
int q,vis[N],f[N][Q];
void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].next){
        int u=edge[i].a ;
        if(vis[u]) continue;
        vis[u]=1;
        dfs(u);   //枚举右子树  //也可以看成背包中的枚举物品
        for(int j=n-1;j>=1;--j){     //保留的边数（除根外的结点数）  //后面这句不用看，从大到小枚举，类似背包 ，这里不用细想记住就好   //也可以看成背包中的枚举体积
            for(int k=0;k<j;++k){   //左子树保留的边数 
                f[x][j]=max(f[x][j],f[x][k]+f[u][j-k-1]+edge[i].len);  //这里可以看成依次枚举左右子树保留的边数
//f[x][j]表示以x为根总共保留j条边  //f[x][k]表示左子树 f[u][j-k-1]+edge[i].len表示右子树 ，相加之后为其合并结果
            }
        }
    }
}
int main(){
    cin >> n >> q;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n-1;++i){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);add(b,a,c);
    }
    dfs(1);
    cout << f[1][q] << endl;
    return 0;
}