题目大意：
国家探险队长 Jack 意外弄到了一份秦始皇的藏宝图，于是，探险队一行人便踏上寻宝之旅，去寻找传说中的宝藏。
藏宝点分布在森林的各处，每个点有一个值，表示藏宝的价值。它们之间由一些小路相连，小路不会形成环，即两个藏宝点之间有且仅有一条道路。探险队从其中的一点出发，每次他们可以留一个人在此点开采
宝藏，也可以不留，然后其余的人可以分成若干队向这一点相邻的点走去。需要注意的是，如果他们把队伍分成两队或两队以上，就必须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的
宝藏。并且，为了节约时间，队伍在前往开采宝藏过程中是不会走回头路的。现在你作为队长的助理，根据已有的藏宝图，请计算探险队所能开采的最大宝藏价值。
注意：在整个过程中，每个人最多只能开采一个点的宝藏。
题目分析：
和选课差不多，可以转成孩子兄弟树，也可以按照拓扑序来进行树上背包（由于一个节点有多个儿子，所以选择由儿子更新父亲）。
\(dp[i][j][0]\)表示在i节点子树中选择j个节点，i节点不选的方案，\(dp[i][j][1]\)表示i节点子树中选择j个点，i节点要选的方案.
每个节点分为两种情况：在其父节点驻守，那么背包即可，否则由儿子直接转给父亲。
code
树上背包
#include<bits/stdc++.h>
using namespace std;
const int N = 150, M = 150;
int n, m, dp[N][M][2];
int ecnt, adj[N], go[N << 1], nxt[N << 1];
int val[N], fa[N], deg[N], ans;
queue<int> que;
inline void addEdge(int u, int v){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
}
inline void dfs(int u, int f){
fa[u] = f;
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
dfs(v, u);
deg[u]++;
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i < n; i++){
int x, y; scanf("%d%d", &x, &y);
addEdge(x, y), addEdge(y, x);
}
for(int j = 1; j <= n; j++)
for(int k = 1; k <= m; k++) dp[j][k][1] = val[j];
dfs(1, 0);
while(!que.empty()) que.pop();
for(int j = 1; j <= n; j++)
if(!deg[j]) que.push(j);
while(!que.empty()){
int u = que.front(); que.pop();
int tmp[M][2];
memcpy(tmp, dp[fa[u]], sizeof tmp);
for(int j = 1; j <= m; j++){
for(int k = m - j; k >= (fa[u] ? 1 : 0); k--){ //驻守在father
dp[fa[u]][k + j][1] = max(dp[fa[u]][k + j][1], tmp[k][1] + max(dp[u][j][1], dp[u][j][0]));
}
dp[fa[u]][j][0] = max(dp[fa[u]][j][0], max(dp[u][j][1], dp[u][j][0])); //不驻守
}
if(!(--deg[fa[u]]) && fa[u]) que.push(fa[u]);
}
printf("%d", max(dp[0][m][1], dp[0][m][0]));
return 0;
}
多叉树转二叉树
#include<bits/stdc++.h>
using namespace std;
const int N = 150;
int n, m;
int val[N], fa[N];
int ecnt, adj[N], nxt[N << 1], go[N << 1];
int dp[N][N][2], son[N], bro[N];
inline void addEdge(int u, int v){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
}
inline void dfs(int u, int f){
fa[u] = f;
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
dfs(v, u);
}
}
inline int DP(int u, int k, int t){
if(!u || !k) return dp[u][k][t] = 0;
if(dp[u][k][t] != -1) return dp[u][k][t];
dp[u][k][t] = 0;
if(t == 1){ //父亲节点被选择
for(int i = 0; i <= k - 1; i++) //选择u
dp[u][k][1] = max(dp[u][k][1], DP(son[u], i, 1) + DP(bro[u], k - 1 - i, 1) + val[u]);
for(int i = 0; i <= k; i++) //不选u
dp[u][k][1] = max(dp[u][k][1], DP(son[u], i, 0) + DP(bro[u], k - i, 1));
}
else { //父亲节点未被选择 ,只能选择一边
dp[u][k][0] = max(dp[u][k][0], max(
max(DP(son[u], k - 1, 1) + val[u], DP(son[u], k, 0)),
DP(bro[u], k, 0)
));
}
return dp[u][k][t];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i < n; i++){
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
dfs(1, 0);
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++) bro[i] = son[fa[i]], son[fa[i]] = i;
printf("%d", max(DP(son[0], m, 1), DP(son[0], m, 0)));
}