Editorial for Baltic OI '03 P2 - Gems
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
This task can be solved by dynamic programming. Let us root the tree by choosing one of the leaves as a root. Then we can process the tree in a bottom-up order. For each vertex we should compute two solutions for a sub-tree rooted in the given vertex:
- the optimal solution, together with the gem
used for the given vertex,
- the optimal solution, assuming, that the given vertex is modeled by a gem different from
Comments