二叉苹果树（树形DP＞＞有依赖的背包问题）

传送门：二叉树苹果树

思路：题意大致为在一棵以1为根节点的二叉树中保留m条边，使得边上的权值加起来最大，转化一下除了1以外的每一个节点都有一个权值，最多保留m个点，使得权值和最大，可变成有依赖的背包问题

状态表示：f[i][j]表示以i为根的这棵树保留j个节点的最大权值。

代码：

#include
#include
#include 
#include
#include 
using namespace std;
const int N=1e3+7;
int n,ans,m;
int f[N][N];
int idx,e[N*2],h[N],ne[N*2],w[2*N];
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int father)
{
    for(int i=h[u];~i;i=ne[i])//先物品组
    {
      if(e[i]==father) continue;
      dfs(e[i],u);
 
      for(int j=m;j;j--)//后体积
        for(int k=0;k+1<=j;k++)//再决策
        f[u][j]=max(f[u][j],f[u][j-k-1]+f[e[i]][k]+w[i]);
 
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<1][m]<
    return 0;
}