1006 二叉苹果树 树上背包

链接：https://ac.nowcoder.com/acm/contest/25022/1006
来源：牛客网

题目描述

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

输入描述:

第一行两个数N和Q，N表示树的节点数，Q表示要保留的树枝数量。
接下来N-1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出描述:

输出仅一行，表示最多能留住的苹果的数量。

示例1

输入

复制 5 2<br />1 3 1<br />1 4 10<br />2 3 20<br />3 5 20

5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出

复制 21

21

备注:

对于100%100 /%100%的数据，1≤Q≤N≤100,N≠11 /le Q /le N /le 100,N /neq11≤Q≤N≤100,N​=1，每根树枝上苹果不超过30000个。

分析

一开始自己写了一些，然后看了雨巨的才知道这叫树上背包，背包的话体积要从最大开始减小，而原来从小到大增大了。

然后发现还是改不出正确答案，看了别人的题解，缝缝补补，

1.在体积的遍历中 删去了 if(k >= sz[j]) continue;体积比叶子节点大就跳过这条限制（现在看来确实有点不合理，后面的还要用到这部分的数据，不然没法传递了。）

2.原来是遍历根节点的所有体积情况，再输出最大值，但是应该直接求根节点最大体积的情况。

树形DP，直接枚举同一个节点不同链的时候的枝叶数量，左边增多右边就减少。

设dp[i][j] 表示节点i 有j 个链的时候的情况

状态转移：dp[i][m] = max(dp[i][k] + dp[j][m-k-1] + w[i]) 表示当前节点选k条链，点前节点的子节点选 m – k – 1 条链，加上到当前节点子节点的链总共 m 条链的最大值。

//-------------------------代码----------------------------

//#define int ll
const int N = 300;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dp[N][N];
int sz[N];
int vis[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 fa) {
    vis[u] = 1;
    for(int i = h[u];~i;i=ne[i]) {
        int j = e[i];
        if(j == fa||vis[j]) continue;
        dfs(j,u);
        sz[u] += sz[j];
        for(int k = m;k>=0;k--) {
            for(int q = 0;q<k;q ++ ) {
                dp[u][k] = max(dp[u][q] + dp[j][k-q-1] + w[i],dp[u][k]);
            }
        }
    }
    sz[u] += 1;
}

void solve()
{
    cin>>n>>m;
    ms(h,-1);
    fo(i,1,n) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);add(b,a,c);
    }
    int ans = 0;
    dfs(1,-1);
    fo(i,0,m) {
        ans = max(dp[1][m],ans);
    }
    cout<<ans<<endl;
}

signed main(){
    clapping();TLE;

//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------