# Help on an unsolved problem

Question

• 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:-

Verdict
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 ?