poj 2486 Apple Tree

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 树上的背包

不要把问题想得太复杂,最初最清晰的思想,尝试用文字表达出来,再转化为代码,可能会比较容易

dp[u][m][0] : 用m步去走u这个子树并且回到u

dp[u][m][1] : 用m步去走u这个子树但不回到u

dp[u][m][0] = max(dp[u][m][0] , dp[v][k][0] + dp[u][m-k-2][0]);

//v是u儿子,既然要回到u,那么如果去任何一个儿子子树的话也是要返回的,所以用儿子子树“返回”的这种状态去更新

dp[u][m][1] = max(dp[u][m][1] , dp[v][k][1] + dp[u][m-k-1][0]);

//v是u儿子,因为在u子树中不返回,但在哪里不返回的我们不知道,我们就假设是在v这个子树的某个地方就停止了不返回

//那么对于u的其他子树部分是返回的,(因为要返回到u才能下去到v,然后才不返回)

dp[u][m][1] = max(dp[u][m][1] , dp[v][k][0] + dp[u][m-k-2][1]);

//v是u儿子,因为在u子树中不返回,但在哪里不返回的我们不知道,但我们假设在v这个子树是返回的,

//那么从v这个子树返回后,回到u,再下去其他分支,此时才不返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 110
#define M 210
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,tot,val[N],dp[N][M][2];
vector<int>e[N];

void dfs(int u ,int fa){
for(int i = 0; i <= tot; i++)
dp[u][i][0] = dp[u][i][1] = val[u];
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
for(int m = tot; m >= 1; m--){
for(int k = 0; k <= m-2; k++)
dp[u][m][0] = max(dp[u][m][0] , dp[v][k][0] + dp[u][m-k-2][0]);
for(int k = 0; k <= m-2; k++)
dp[u][m][1] = max(dp[u][m][1] , dp[v][k][0] + dp[u][m-k-2][1]);
for(int k = 0; k <= m-1; k++)
dp[u][m][1] = max(dp[u][m][1] , dp[v][k][1] + dp[u][m-k-1][0]);
}
}
}

int main(){
while(scanf("%d%d",&n,&tot)!=EOF){
for(int i = 1; i <= n; i++)
scanf("%d",&val[i]);
for(int i = 1; i <= n; i++)
e[i].clear();
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
cl(dp,0);
dfs(1,-1);
printf("%d\n",max(dp[1][tot][0],dp[1][tot][1]));
}
return 0;
}