Maximum Path Sum Problem Statement

You are given an n-ary tree consisting of 'N' nodes. Your task is to determine the maximum sum of the path from the root to any leaf node.

Example:

Input:

For the given tree:

The path 1 -> 3 -> 7 produces the maximum, i.e., 11.

Input:

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The second line of each test case contains elements of the N-ary tree in level order. The values of nodes are separated by a single space. If a node is absent, it is represented by -1. The first non-null node (of the previous level) acts as the parent of the first node in the current level. Similarly, the second non-null node (of the previous level) acts as the parent of the subsequent nodes of the current level, and so forth.

Output:

For each test case, print the maximum sum of the path from the root to the leaf node.

Print the output of each test case in a separate line.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5000
• 0 <= DATA <= 10⁴

Where 'T' is the number of test cases, 'N' is the total number of nodes in the binary tree, and 'DATA' is the value of the tree node.

Time Limit: 1 sec