my email: yuwei110@yahoo.com.cn

Please somebody explain me too, how to solve this problem.
Thank's!!!

my e-mail: r86acm@ukr.net

Edited by author 11.08.2005 14:49

  We can imagine that there's also a branch (or a trunk ^_^) below the root node, on which of course there are no apples at all. We denote by dp[x,y] the number of apples we can keep if we can keep y edges on the subtree with root x and the branch right below x.
  If y=0, then dp[x,0]=0.
  If y=1, then the branch right below x must be kept, so dp[x,1]=the number apples on the branch right below x.
  If y>1, then you can use enumeration to determine how many apples to keep on the two subtrees of x. Let a and b be the two children of x, then dp[x,y]=max{dp[x,1]+dp[a,i]+dp[b,y-1-i]}.
  The complexity is obviously O(n^3).
  Good luck!

P.S. To Roman: I wonder why I can't send you e-mail from my Chinese mailbox. In the future you could send questions into this Japanese mailbox: akisame1988@yahoo.co.jp.

At last I solved that problem!

Edited by author 28.08.2005 02:42