How should I practice Maximum Nonadjacent Sum in a General Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Zip phone screen and onsite interview problems in FastPrep.

Is Maximum Nonadjacent Sum in a General Tree associated with Zip?

FastPrep tags this as a Zip phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Maximum Nonadjacent Sum in a General Tree

Zip● MediumFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Each node in a rooted tree has a nonnegative value. Choose any set of nodes with the largest possible total value, subject to one rule: a chosen node and its direct child cannot both be chosen. The tree can have any number of children per node.

The input nodes[i] = [value, parent] describes node i. Node 0 is the root and has parent -1. For every other node, its parent appears earlier in the array. Return the maximum total. Choosing no nodes is allowed.

Function

maxTreeSum(nodes: int[][]) → int

Examples

Example 1

nodes = [[5,-1],[4,0],[6,0],[7,1],[2,1],[3,2]]return = 17

Choosing the root, both grandchildren of node 1, and the grandchild of node 2 gives 5 + 7 + 2 + 3 = 17.

Example 2

nodes = [[1,-1],[10,0],[10,0],[10,1],[10,2]]return = 21

Choosing the root and both leaf grandchildren gives 21; choosing the two children gives 20.

Constraints

1 <= nodes.length <= 10000.
Each row contains exactly two integers: [value, parent].
0 <= value <= 1000.
nodes[0][1] == -1; for i > 0, 0 <= nodes[i][1] < i.
The answer fits a signed 32-bit integer.