Pattern: 3dsa + 12 MCQS 90 min

You are given a tree structure represented by two arrays: parent and value.

• parent[i] denotes the parent node of node i. The root node will have a parent of -1.
• value[i] denotes the integer value associated with node i.

You need to convert this given array format into a tree and find the maximum path sum within it. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. Each node can be used at most once in the path.

Input Format

• The first line contains an integer N, the number of nodes.
• The second line contains N space-separated integers representing the parent array.
• The third line contains N space-separated integers representing the value array.

Output Format

• Print a single integer representing the maximum path sum.

Example Input:

4
-1 0 1 2
2 5 22 -1

Output:

29

Explanation:

The graph forms a line: Node 0 (val 2) → Node 1 (val 5) → Node 2 (val 22) → Node 3 (val -1). The path yielding the maximum sum includes nodes 0, 1, and 2. Sum = 2 + 5 + 22 = 29.