All problems

Festival Lights Tree

Medium · tree dp

The town of Marrowby is getting ready for its lantern festival. Every lantern hangs on a pole, and the poles are joined by cables into a binary tree: the main pole by the fountain is the root, and each pole is wired down to at most two poles below it. Every pole carries a lantern, and the value at a pole says how bright its lantern shines.

There is one problem. The cables are old, and if two poles that share a cable are both lit, the fuse blows. So no two poles joined directly by a cable may be lit at the same time. Poles that are only connected through a third pole are fine, and any pole may be left dark.

Choose which poles to light so that the total brightness is as large as possible, and return that total. If there are no poles, the total is 0.

Examples

Example 1

Input: root = [4, 1, 6, 8]

Output: 14

Light the poles worth 6 and 8. They sit on different branches and share no cable, so both can stay on. Lighting the root as well is not allowed with 6.

Example 2

Input: root = [10, 9, 9]

Output: 18

Each child is joined to the root, so lighting the root rules out both of them. The two children together beat the root alone.

Example 3

Input: root = [5, 1, 1, 6, null, null, 6]

Output: 17

Light the root and both poles at the bottom: 5 + 6 + 6. None of them shares a cable with another.

Constraints