这道题一开始是按照caioj上面的方法写的
（1）存储二叉树用结构体，记录左儿子和右儿子
（2）把边上的权值转化到点上，离根远的点上
（3）用记忆化搜索，枚举左右节点分别有多少个点，去递归
这种写法有个好处， 避免了总的树枝个数的枚举
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
struct node
{int v, w; node(int v = 0, int w = 0) : v(v), w(w) {}
};
struct tree
{int l, r;tree() { l = r = 0; }
}a[MAXN];
vector<node> g[MAXN];
int f[MAXN][MAXN], n, q;void dfs(int x, int fa)
{REP(i, 0, g[x].size()){int v = g[x][i].v, w = g[x][i].w;if(v == fa) continue;f[v][1] = w;if(!a[x].l) a[x].l = v;else a[x].r = v;dfs(v, x);}
}int tree_dp(int x, int k)
{if(x == 0) return 0;if(f[x][k] != -1) return f[x][k];int maxt = 0;REP(i, 0, k){int ls = i, rs = k - i - 1;maxt = max(maxt, f[x][1] + tree_dp(a[x].l, ls) + tree_dp(a[x].r, rs));}return f[x][k] = maxt;
}int main()
{scanf("%d%d", &n, &q);REP(i, 0, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node(v,w));g[v].push_back(node(u,w));}memset(f, -1, sizeof(f));dfs(1, -1);REP(i, 1, n + 1) f[i][0] = 0;f[1][1] = 0;printf("%d\n", tree_dp(1, q + 1));return 0;
}然后看到洛谷上还有更加简洁的写法
先往下搜索，然后回溯的时候记录边的数量，然后枚举左右节点
取多少树枝，取max。
f[u][j] = max(f[u][j-k-1] + f[v][k] + w);
然后这里用到了01背包的思想
树枝可以看成从的总的重量，所以要逆序
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
struct node
{int v, w; node(int v = 0, int w = 0) : v(v), w(w) {}
};
vector<node> g[MAXN];
int f[MAXN][MAXN], b[MAXN], n, q;void dfs(int u, int fa)
{REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(v == fa) continue;dfs(v, u);b[u] += b[v] + 1;for(int j = min(q, b[u]); j >= 0; j--)for(int k = 0; k <= min(b[v], j - 1); k++)f[u][j] = max(f[u][j], f[u][j-k-1] + f[v][k] + w);}
}int main()
{scanf("%d%d", &n, &q);REP(i, 1, n){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node(v,w));g[v].push_back(node(u,w));}dfs(1, 0);printf("%d\n", f[1][q]);return 0;
}
做完了选课在来看这一题，又有新的感悟。
树上背包的做法适用于多叉树和二叉树，二叉树是两个物品，多叉树是多个物品。
而这道题有一点不同是权值是边。那么吸取上面写的经验。
我们可以把边的权值转移到离根远的点上，同时可以取的点数为边数+1
然后就一样啦！！
#include<cstdio>
#include<vector>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
int f[MAXN][MAXN], n, q;
struct node
{int v, w;node(int v = 0, int w = 0) : v(v), w(w) {}
};
vector<node> g[MAXN];int dfs(int u, int fa)
{int sum = 1;REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(v == fa) continue;f[v][1] = w;int t = dfs(v, u);sum += t;for(int j = sum; j >= 1; j--)for(int k = 0; k <= min(t, j - 1); k++)f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);}return sum;
}int main()
{scanf("%d%d", &n, &q);REP(i, 0, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node(v, w));g[v].push_back(node(u, w));}dfs(1, -1);printf("%d\n", f[1][q+1]);return 0;
}