题目大体上也算是一个树上背包的问题，只不过有个细节需要特别注意一下
父亲如果想要儿子的苹果，那么父亲和儿子之间必须要连接起来
设 f[u][j] 代表以 u 为根节点 保留 j 条边的最大价值
根据树上背包的转移方程我们很容易知道
f[u][j] = max(f[u][j] , f[v][k] + f[u][j-k] )
但是这里要注意我之前说的那个细节 父亲如果想要儿子的苹果，那么父亲和儿子之间必须要连接起来
所以儿子取 k ，父亲要取 j - k - 1 （留一条边连接父亲与儿子）
f[u][j] = max(f[u][j] , f[v][k] + f[u][j-k-1] + val ) val 就是父亲和儿子连接的边权
#include <iostream>#include <algorithm>#include <string>#include <string.h>#include <vector>#include <map>#include <stack>#include <set>#include <queue>#include <math.h>#include <cstdio>#include <iomanip>#include <time.h>#include <bitset>#include <cmath>#define LL long long#define INF 0x3f3f3f3f#define ls nod<<1#define rs (nod<<1)+1const double eps = 1e-10;const int maxn = 310;const LL mod = 1e9 + 7;int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}using namespace std;struct edge { int v,nxt;}e[maxn];int head[maxn];int c[maxn][maxn],f[maxn][maxn];int cnt,n,q;void add_edge(int u,int v) { e[++cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt;}void dfs(int x) { for (int i = head[x];~i;i = e[i].nxt) { int v = e[i].v; dfs(v); for (int j = q;j >= 1;j--) { for (int k = j-1;k >= 0;k--) f[x][j] = max(f[x][j],f[v][k]+f[x][j-k-1]+c[x][v]); } }}int main() { cnt = 0; memset(head,-1, sizeof(head)); cin >> n >> q; for (int i = 1;i < n;i++) { int u,v,w; cin >> u >> v >> w; c[u][v] = w; add_edge(u,v); } dfs(1); cout << f[1][q] << endl; return 0;}
