Uber OA 2023 - Maximum Number Of Fruits

Problem Description

You have a healthy tree with N nodes rooted at node 1, where each node has a certain number of fruits attached to it. In one operation, you can collect all the fruits from a node and keep them for yourself.

A tree is considered healthy if there is at least one node with fruits from the root node to every leaf node.

Your task is to output the maximum number of fruits you can collect from the tree while maintaining its healthiness.

Input Format

• An integer n: The number of nodes in the tree.
• An array of integers tree of size n: Every element defines the parent of the i-th node. The value will always be 0 for the root node.
• An array of integers fruits of size n: Every element defines the number of fruits attached to the ith node.

Output Format

• An integer64: The maximum number of fruits you can collect from the tree.

Constraints

• 1 <n≤ 100,000
• 0<A[i]≤10^9

Sample Test Case

Input

n = 5
tree = [0, 1, 1, 2, 2]
fruits = [7, 4, 2, 3, 4]

Output

15

Explanation

You can collect fruits from nodes 1, 4, and 5. The tree will still remain healthy as from the root node to every leaf, there is at least one node with fruits.