Hello,

Recently I gave a coding interview test at a company. This was one of the problem I was unable to solve. Can anyone please guide me through the approach and the solution.

This was the problem statement :-

Hydrate the nodes There is a tree with n nodes. The tree is rooted at node with number 0. As usually in computer science, the tree grows upside down comparing to trees existing in nature. Apples grow on nodes of this tree. Some of these apples are underhydrated, some are overhydrated, and others are neither. You know that for each overhydrated apple you'll get overhydratedPenalty cents and for every underhydrated you'll get underhydratedPenalty cents. Now, you want to pour water on exactly one node of the tree. When you pour water on node v, all apples that are in v's subtree, i.e. vitself and all descendants of v, will be hydrated and in consequence, each hydrated apple that was almost overhydrated becomes overhydrated. Moreover, every apple in the whole tree that was almost underhydrated and no water was poured on it gets underhydrated. Calculate the minimum total penalty you can get from pouring water on exactly one node of the tree.

Function Description Complete the function minimumPouringWaterPenalty(vector parent, vector waterLevel, int overhydratedPenalty, int underhydratedPenalty)

minimumPouringWaterPenalty has the following parameter(s): 1. An integer array, parent, of size n, where parenti, denotes the parent of the ith node. 2. An integer array, waterLevel, of size n, where waterLevel denotes the level of the water in the apple on node i. It's either -1, 0 or 1 where -1 stands for almost underhydrated, O stands for neither almost underhydrated nor almost overhydrated and 1 stands for almost overhydrated. 3. An integer, overhydratedPenalty, denoting the penalty for each overhydrated apple. 4. An integer, underhydrated Penalty, denoting the penalty for each underhydrated apple.

The function must return the minimum penalty that you can get by pouring water on exactly one node of the tree.

Text taken from : https://codeforces.com/blog/entry/86512

I know that this has to be done using DFS/BFS, but I'm unable to comeup with solution. Any hint will also be fine.

Thanks.