All problems

Scenic Cable Tour

Hard · tree dp

A valley is served by a network of cable cars. The stations form a binary tree: the station at the foot of the valley is the root, and each station is linked by cable to at most two stations higher up, one to the left and one to the right. Each station has a score for how pleasant it is to stop there. A score can be negative, for a noisy or crowded stop.

A tour is a trip along the cables that visits a line of stations: it starts at any station, then moves from station to station along a cable, up or down, and never visits a station twice. A tour of a single station is allowed. Its total is the sum of the scores of all the stations on it.

The ticket office will only sell tours with at most limit stations. Return the largest total any tour can have.

Examples

Example 1

Input: root = [-4, 5, 6, 3, -2, 7], limit = 3

Output: 13

The tour 7 -> 6 has two stations and totals 13. Going on to the station -4 would lower it to 9, and the four-station tour 7 -> 6 -> -4 -> 5 would total 14 but is over the limit.

Example 2

Input: root = [2, -1, 3], limit = 1

Output: 3

With one station the best tour is the best single score.

Example 3

Input: root = [-3], limit = 5

Output: -3

A tour has to visit at least one station, so even a negative score is the answer.

Constraints