二叉苹果树 【树形dp(背包)】

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

题目描述

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

输入描述:

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

输出描述:

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

示例

输入

5 2

1 3 1

1 4 10

2 3 20

3 5 20

输出

21

备注:

对于100%的数据，1 ≤ Q ≤ N ≤ 100,N ≠ 1，每根树枝上苹果不超过30000个。

 思路：

1. 题意解读：

剪掉一根枝条后，它所连的下面的所有枝条都会没有（根在上）；

2. 数据存储：

题意所述的“权值”其实为边权，但用边权表示并不方便，考虑到一条边如果不存在了，那么它下面所连的点也将不复存在，于是每一条边的值可以“下放”到它所属的点上。

3. 状态转移：

令 f[x][j] 表示以 x 为根节点的子树总共有 j 条边的最大权值（苹果树量），，则分为以下三种情况：（x 的左子节点用 left 表示，右子节点用 right 表示，apple[x][y] 表示连接点x 和 y的枝条上的苹果数）【注意此处的apple[x][y]为了方便表示，与下面代码里的app表示方式不一样，但意义都是父节点到该子节点的权值w】

• 【j条边全在左边，右边为0】：left 点以下有 j-1 条边，因为点 x 到点 left算一条边。则：f[x][j] = max( f[x][j], f[left][j-1] + apple[x][left] ).
• 【j条边全在右边，左边为0】：同理，f[x][j] = max(f[x][j], f[right][j-1] + apple[x][right]).
• 【左右都有】：设 left 点以下有 k 条边，则 right 点以下有 j - k - 2 条边，因为还要加上" x->left"这条边和"x->right"这条边，则：f[x][j] = max(f[x][j], f[left][k] + f[right][j-k-2] + apple[x][left] + apple[x][right] ).

4.拓展版：二叉树-->多叉树

如果有 n 叉，难道我们也要全部列出来吗？一根枝条有选和不选两种可能，那么 n 根则要列举 种（减一是去掉“都不选”的情况），这时候的问题就像是，把枝条上的苹果数看成“价值”，枝条数目看成限制条件：“体积”，则就是在 n 个物品中选取若干价值不同的物品，选或不选，在体积为 q 的情况下求最大价值——典型的“背包问题”！

状态转移方程：

f[x][j]=max(f[x][j],f[x][k]+f[y][j-k-1]+w);

在已经选取 k 根枝条的情况下不断加入新的枝条，注意，与普通背包问题一样，k 要从大到小枚举以防止“ 重复选择（多重背包）”。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,q,f[110][110];
vector<int> edge[110],app[110];
void dfs(int x,int fa){//复杂度: O(n^3)for(int i=0;i<edge[x].size();i++){int y = edge[x][i];if(y==fa)continue;dfs(y,x);for(int j=q;j>=0;j--){//树上背包，从大到小 for(int k=0;k<j;k++){f[x][j]=max(f[x][j],f[x][k]+f[y][j-k-1]+app[x][i]);//app[x][i]就是点x到y的边权，此处不是以序号来索引，是与y一同在第i次时push进去的。}}}
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1,x,y,z;i<n;i++){cin>>x>>y>>z;edge[x].push_back(y);app[x].push_back(z);//x->y的权值为app[x][i]edge[y].push_back(x);//双向边 app[y].push_back(z);}dfs(1,0);cout<<f[1][q];return 0;
}

可以把上述代码中的edge 和 app 合成一个pair来写以方便“调用”：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int M=110;
int n,q,f[M][M];
vector<pair<int,int> >ve[M];
void dfs(int x,int fa){for(auto p:ve[x]){//（for循环的简写，“范围遍历”）int y=p.first, w=p.second;if(y==fa)continue;dfs(y,x);for(int j=q;j>=0;j--)for(int k=0;k<j;k++)f[x][j]=max(f[x][j],f[x][k]+f[y][j-k-1]+w);}
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1,x,y,z;i<n;i++){cin>>x>>y>>z;ve[x].push_back({y,z});ve[y].push_back({x,z});}dfs(1,0);cout<<f[1][q];return 0; 
}