POJ 2468 Apple Tree 树上瞎搞分组背包

昨晚debug了好久始终找不出哪里错了，今早再一看发现自己已荣升逗比beta 2.0 version.

个人感觉此题为hdu 4003 的弱化版。

把每棵子树都看成一类商品，在每类商品中至多选一件。则问题转化为最基本的分组背包问题。

dp[s][c][k] c == 1时，表示在s结点不返回时走k的最大收益，c == 0时，表示在s结点重新返回时走k步的最大收益。

可以dfs从底到顶更新dp。值得一提的是，要保证每个结点的dp[s][c][k]只会被dfs一次，即不能重复更新。

因为重复的dfs不能保证每类商品中之多选一件。