Maximize non-adjacent sum on an N-ary tree

You are given an N-ary tree (each node may have 0..k children). Each node contains an integer value (can be 0 or positive).

You want to select a set of nodes such that no selected node is directly connected to another selected node (i.e., you cannot select both a node and any of its children). Return the maximum possible sum of selected node values.

Requirements

• Implement a tree node structure yourself, e.g.:
  • value: int
  • children: List[Node]
• Write a function maxNonAdjacentTreeSum(root) -> int.

Input / Output

• Input: root pointer/reference to the root node (or null for empty tree).
• Output: an integer representing the maximum achievable sum.

Example

If the tree is:

• Root 3 with children 2 and 3
• Node 2 has child 3
• Node 3 (child of root) has child 1

One optimal selection is nodes with values 3 (root) + 3 (grandchild under 2) + 1 = 7, so return 7.

Constraints

• Number of nodes n up to ~10^5.
• Aim for O(n) time.
• Extra space should be proportional to recursion depth or explicit stack size.

Maximum Non-Adjacent Sum on an N-ary Tree

Given nodes as [value, child_indices] and a root index, return the maximum sum selecting no parent-child pair together.

Hints

1. Choose a representation that makes the core operation simple.
2. Handle empty and boundary inputs before the main algorithm.