You are given the root of an N-ary tree. Each node has an integer field val and a list children containing zero or more child nodes.
A path is a sequence of distinct nodes such that every consecutive pair is joined by an edge. The path may begin and end at any nodes in the tree. A path consisting of exactly one node is allowed.
Return the maximum sum of val values over all valid paths.
In the examples, a node is written as [value, [children]].
Example 1:
Input:
root = [4, [[-2, []], [7, [[6, []], [-5, []]]], [3, []]]]
Output:
20
Explanation: The path 6 -> 7 -> 4 -> 3 has sum 20, which is the largest valid total.
root = [4,20
The input tree: root 4 has children -2, 7, and 3; node 7 has children 6 and -5.
Example 2:
Input:
root = [-20, [[5, [[8, [[-3, []]]], [2, [[-1, []]]]]]]]
Output:
15
Explanation: The optimal path stays inside the subtree rooted at 5: 8 -> 5 -> 2 totals 15. Including the negative root or negative leaves would reduce the sum.
Example 3:
Input:
root = [-6, [[-2, []], [-9, []]]]
Output:
-2
Explanation: All values are negative, so the best path is the single node with the largest value, -2.
Constraints:
root = [4,20
The input tree: root 4 has children -2, 7, and 3; node 7 has children 6 and -5.