Loading...
Loading...
Loading...
At the college tech fest, the treasure hunt has rooms joined like a tree. Each room gives points, or takes them away when the number is negative. A team picks any path: a start room and an end room, walking along the links without visiting a room twice. It collects the points of every room on the path, including both ends.
The path has at least one room, and it may start and end anywhere. Print the largest total a team can collect.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. The tree has at least one node.Example 1
Input
-10 9 20 N N 15 7
Output
42
The path 15 → 20 → 7 gives 42. Adding -10 and 9 would give 41.
Example 2
Input
-3 -1 -2
Output
-1
Every room takes points away. The best a team can do is the single room -1.
Try the problem first. Open one hint at a time.
Every path has one highest room. From there it goes down at most one line on the left and at most one line on the right.
For each room, find the best gain of a line that starts there and goes straight down. A line going up to the parent can use only one side.
A side whose best gain is negative only hurts: treat it as 0, which means not going that way.
At each room, update the answer with room + left gain + right gain. Start the answer at the smallest int, not at 0.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor