title: Hyderate the Nodes
body: <p>Recently I gave a coding interview test at a company. This was one of the problem I was unable to solve. I tried on my own and came with approach but I'm not sure if it's correct, please help me rectify my mistake in approach if any.</p>
  <p>This was the problem statement :-</p>
  <p>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.</p>
  <p>Function Description Complete the function minimumPouringWaterPenalty(vector parent, vector waterLevel, int overhydratedPenalty, int underhydratedPenalty)</p>
  <p>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.</p>
  <p>The function must return the minimum penalty that you can get by pouring water on exactly one node of the tree.</p>
  <p>Text taken from : <a href="https://codeforces.com/blog/entry/86512" rel="nofollow noreferrer">https://codeforces.com/blog/entry/86512</a></p>
  <p>My approach :</p>
  <ol>
  <li>Make Graph with parent[i] -&gt; i (<strong>g</strong>)</li>
  <li>Do dfs traversal to check penalty at each node if that node is given water. In this just checking if any value is 1 then increase count penalty of overhyderate for that node and store in array(<strong>h_penalty</strong>) for each node what is penalty if water is given.</li>
  <li>Traverse again this time check if water is not given then what is penalty for underhyderate. In this just checking if any value is -1, then increase count of penalty of underhyderate for that node and store in array(<strong>u_penalty</strong>) for each node what is penalty if water is given.</li>
  <li>Now, I have penalty of each node if water is given and if water is not given. Then I will traverse h_penalty and and for each node I will take minimum of h_penalty[i] + (u_penalty[0]-u_penalty[i]).</li>
  </ol>
  <p>Here is my code for approach :</p>
  <pre><code>from collections import defaultdict
  
  
  def hyderatedtheNode(parent, waterLevel, overHyderatd, underHyderated):
      g = defaultdict(list)
  
      h_penalty = [0] * len(waterLevel)
      u_penalty = [0] * len(waterLevel)
  
      createGraph(parent, g)
      dfs(0, waterLevel, overHyderatd, underHyderated, 1, h_penalty, g)
      dfs(0, waterLevel, underHyderated, overHyderatd, - 1, u_penalty, g)
      # print(h_penalty)
      # print(u_penalty)
      # print(g)
      # print(list(enumerate(waterLevel)))
      ans = float('inf')
      p = u_penalty[0]
      for i, h in enumerate(h_penalty):
          ans = min(ans, h + (p - u_penalty[i]))
      print(ans)
  
  
  def createGraph(parent, g):
      for i in range(1, len(parent)):
          g[parent[i]].append(i)
  
  
  def dfs(src, waterLeve, oH, uH, apple, val, g):
      if not g.get(src, None):
          if waterLeve[src] == apple:
              val[src] = oH
              return oH
          return 0
  
      if g.get(src, None):
          penalty = 0
          if waterLeve[src] == apple:
              penalty = oH
          for t in g[src]:
              penalty += dfs(t, waterLeve, oH, uH, apple, val, g)
              # print(src, t, penalty)
      val[src] = penalty
      return penalty
  
  
  hyderatedtheNode([-1, 0, 1], [1, 1, 1], 3, 5)  # 0
  hyderatedtheNode([-1, 0, 0], [1, -1, -1], 10, 15)   # 10
  hyderatedtheNode([-1, 0, 0, 1], [0, 0, 0, 0], 10, 15)  # 0 
  hyderatedtheNode([-1, 0, 1, 0, 1, 2, 2, 2, 5, 5], [-1, -1, 0, -1, 0, 0, 1, 0, 0, 1], 2, 3)  # 4
  </code></pre>
  <p>Please let me know if this approach is fine or any thing else is needed ?</p>