First move apples to point...
like the sample :
5 2
1 3 1
1 4 10
2 3 20
3 5 20
apple[3]=1 , apple[4]=10 , apple[2]=10 , apple[5]=10..

dp [ f ] [ j + i ] = Max( dp [ f ] [ j + 1 ] ,dp [ f ] [ j ] + dp [ h ] [ i ] +apple [ h ] )

dp [ k ] [ i ] means k is a tree's root,it has i lines..gets the max value...
" f " is h's father...just like this...from leaf to root to update the value..
in the end,print the answer: dp [ 1 ] [ q + 1 ]


Edited by author 25.09.2011 10:11