Help on an unsolved problem


  • Given an N- ary tree with N nodes (N <= 500). Each nodes contains some value (val <= 100).
  • We have to modify the tree such that for each node of the tree, all the subtree of that node should have the same sum.
  • For modification, we can only reduce the values of the node.
  • We have to achieve this with minimum number of reductions.
  • We have to report the sum of the node values of the required tree.

My approach

  • I created a directed graph to represent the tree
  • I performed a dfs to calculate the sum of the initial tree given and stored it as maxSum.
  • Next I created a 2D dp array with dimensions [N+1][maxSum+1]
  • Next I wrote a recursive a function that would take the node index and a sum and would return whether it is possible to achieve that particular sum in tree formed by that node and its subtree.
  • Next I wrote a for loop that ran from maxSum to 0 and called the recursive function with parameters recurse(1->nodeIdx, requiredSum). If the recursive function returned true that that particular Sum would be my answer.
    The boilerplate of my recursive function was like this:-

This code was giving correct answer for the largest test case also, but on submitting overall it was giving TLE.

Can anyone tell a better approach to this problem that would pass within Time Limit ?