Problem Statement

Given a tree with node 0 as the root and a value assigned to each node, determine the maximum sum of values along any path in the tree. The path must not be empty and does not necessarily have to pass through the root. Consider the tree below (labelled with node number/value ): node 0/5 is connected to 1/7 and 4/15 ; node 1/7 is connected to 2/-10 ; node 2/-10 is connected to 3/4 . Two of the possible paths are 4 → 0 → 1 → 2 → 3 with a sum of 15 + 5 + 7 + -10 + 4 = 21 , and 1 → 2 → 3 with a sum of 7 + -10 + 4 = 1 . A third possible path, the maximum sum path, is 4 → 0 → 1 with a sum of 15 + 5 + 7 = 27 . Input Format Line 1: the integer n , the number of nodes. Line 2: n space-separated integers parent[0..n-1] , where parent[i] = j means node j is the parent of node i , and parent[0] = -1 marks node 0 as the root. Line 3: n space-separated integers values[0..n-1] , where values[i] is the value of node i . Output Format Print a single integer: the