Tree Question Asked in Uber OA
Anonymous User
378

Given a healthy tree with N nodes rooted at node 1 and each node having some number of fruits attached to it. In one operation you can collect all the fruits of a node and keep it to yourself. While performing this operation, you need to make sure that the tree always remains healthy.
A tree is called healthy if from the root node to every leaf node, there is at least one node with some number of fruits.
Output the maximum number of fruits you can collect from the tree.

Sample Input:

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

output: 14
Explanation:
You can take fruits from nodes 1,4,5. The tree still remains healthy, as from root to every leaf, there is at least one node with fruits

Constraints:
1<=n<=1e5

Input explanation:
Tree Array: Every element defines the parent of the ith node. For 1, the value will always be 0 as it is the root node. GIve tree can be n-ary i.e a node of a tree can have any number of child nodes

Fruits Array: Evert element defiens the number of fruits for the ith node.
0<Ai<=1e9

Comments (3)