Maximum Nonadjacent Sum in a General Tree

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.

The trick is two values per node: best sum if you take it, and best sum if you skip it. Take means value plus the sum of each child's skip. Skip means the sum over children of max(take, skip). The answer is max(take, skip) at the root. Since every parent index is less than its child index, you don't need recursion at all. Build the children lists or just iterate i from n-1 down to 1, adding each node's result into its parent's accumulators. That dodges stack overflow on a 10000-node chain, which is the classic pitfall here. The other mistake is greedy, like picking every other level. Example 2 shows why that fails. Initialize take[i] to value[i] and skip[i] to 0, then fold children upward. StealthCoder is the hedge if the DP recurrence slips away under the clock.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.