二叉苹果树

简化版的书上背包

思路:对于以任意节点为根的子树，可以将子树按与根相连的边分组，不同组内所有的子树的可能即为有特定价值与体积的物品。要求以1为根的所有子树中含有j条枝的最大权值树，问题可以转化为从按1为根分组的所有子树中选放入体积为j的背包的所有选法的maxn，然后即可以用分组背包的思路求解,每组中可不选，选第一个，选第二个，balabalabala...
【注】:分组背包问题循环遵循:(一般便于空间降维处理)
for(分组)
for(体积)
for(决策)

AC代码

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
inline int lowbit(int x) {return x & -x;} 
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 210, mod = 1e9 + 7;
int n, m;
int h[N], nex[N], v[N], w[N], idx;
void add(int a, int b, int c) {
    v[idx] = b; nex[idx] = h[a]; w[idx] = c; h[a] = idx ++ ;
}

int f[N][N];   
//f[i][j]:以i为根的子树中且含j条枝的所有方案的最大权值
void dp(int u, int fa) {
    for(int i = h[u]; ~i; i = nex[i]) {        //组别
        int e = v[i];
        if(e == fa) continue;
        dp(e, u);
        for(int j = m; j; j -- ) {    //体积 此处状态表示少开了一维组别，故从大到小枚举ti'ji
            for(int k = 0; k < j; k ++ ) { //决策
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e][k] + w[i]);                            
            }
        }
    }
} 

int main() {    
    mset(h, -1);
    cin >> n >> m; 
    rep(i, 1, n - 1) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c); add(b, a, c); 
    }

    dp(1, -1);

    cout << f[1][m] << endl; 

    return 0;
}

代码转移方程说明
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e][k] + w[i]);
因为进行了降维处理，故max运算左边代表不选当前这组，从当前组之前的组中选的最优解，
max运算右边代表选择当前这组，但因为此时还有一条与当前根相连的边要选上，故背包体积需要预留1单元，故为j - k - 1，而f[e][k]表示当前选择物品的价值