Maximum Path Sum in a Tree - Zomato Eternal Online Assessment MANIT Bhopal

Problem Preview

"### 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: ```plaintext 4 -1 0 1 2 2 5 22 -1 ``` ### Output: ```plaintext 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."