#244MediumDynamic Programming· Tree DP: Take or Skip

Max Non-Adjacent Tree Bonus

A company hands out bonuses along its management chart, which is a binary tree: every employee has at most two direct reports. Employee `v` is worth a bonus of `value(v)` to the company's goodwill score. Because of a fairness rule, no employee may receive a bonus if their direct manager or one of their direct reports also receives one. Choose the employees that get a bonus so that the **total goodwill is as large as possible**, and return that total. Choosing nobody is allowed.

Input format

`root`: the management chart as a binary tree in level order, with `null` for missing children (an empty array is an empty company).

Output format

A single integer: the largest total value of a set of employees in which no two are directly linked.

Examples

Input: root = [3, 2, 3, null, 3, null, 1]

Output: 7

Choose the root (3) and the two bottom nodes (3 and 1): 3 + 3 + 1 = 7. Choosing the two middle employees gives only 5.

Input: root = [3, 4, 5, 1, 3, null, 1]

Output: 9

Choosing the root and its grandchildren gives 3 + 1 + 3 + 1 = 8. Choosing the two children of the root, 4 and 5, gives 9, which is better.

Input: root = []

Output: 0

Nobody works there, so the total is 0.

Constraints

0 <= number of nodes <= 3000
0 <= value <= 10^4

#tree
#dynamic-programming
#dfs
#independent-set