[andrewcooke]

well, before i realised i had missed the sum part (which i suspect was added to foil lazy people like me) i would have argued that perhaps they are looking for someone who knows enough about the tools already available to find the fastest solution.

not that i have anything against the approaches here - the dynamic programming approach over trees is really cool and i probably wouldn't have thought of it myself. i just thought it amusing that there seemed to be a simpler way.