二叉苹果树

因为是枚举的每个分支,就是不可能在一个分支没选完就选第二个分支,然后转移就很合理了.就是两个分支可以看成01背包,然后保留多少个可以看成背包容量..就没了

#include <bits/stdc++.h>
using namespace std;
const int N=105;
struct vv{
    int to,val;
};
vector<vv>v[N];
int dp[N][N];//以i为根节点 保留j的数量能获得的最大价值.
int n,q;
void dfs(int u)
{
    for(int i=0;i<v[u].size();i++)//枚举节点
    {
        int x=v[u][i].to;
        dfs(x);
        for(int j=q;j>=1;j--)
        {
              for(int k=j-1;k>=0;k--)
              {
                  dp[u][j]=max(dp[u][j],dp[x][k]+dp[u][j-k-1]+v[u][i].val);
              }
        }
    }
}

int main()
{
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        v[x].push_back({y,w});//建边
    }
    dfs(1);
    cout<<dp[1][q]<<endl;
    return 0;
}