poj 2486 Apple Tree 树形背包入门

缘起

研究树形背包~ poj 2486 Apple Tree

分析

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
一颗树，n个点（编号1~n），n-1条边，每个点上有一个权值，求从1出发，走k步，最多能遍历到的权值
ps: 每个点权对权值和最多只能贡献一次

【输入】
多样例. 每个样例由n,k开始, 
1<=N<=100, 0<=K<=200
然后是n个整数，每个整数范围是[0,1000], 然后是n-1行, 每行2个整数表示某两个顶点毗邻

【输出】
最大权值

【样例输入】
2 1 
0 11
1 2
3 2
0 1 2
1 2
1 3

【样例输出】
11
2

【限制】
1s

很典型的树形DP, 我们把背包的思想用到这里来，走的步数相当于背包的容量，点上的权值相当于价值，给定一定的背包容量，求最多能装进背包的价值.

问题在于，如果想到别的孩子去，还要回到根, 所以令

1
2
dp[i][j][0] 表示从节点i出发，走j步，最终回到i节点，所能得到的最大收益 
dp[i][j][1] 表示从节点i出发，走j步，最终不回到i节点，所能得到的最大收益