Given a multi-ary tree with N nodes. We start traversing from the root node with a value of 1. For each node to have a value V with n children, we have to assign ${V*1, V*2, V*3, …, V*n}$ values to all the children nodes in such a way that the sum of all the nodes of the tree is minimum.

The recurring relationship I’ve formed is:

$f(node, factor) = min(f(childnode, value*factor) + value*factor)$

where childnode is ${C_1, C_2, C_3, …, C_n}$ and value is ${1, 2, 3, …, n}$

Also, $f(node, value) = 0$ for all leaf nodes. We have to find $f(root, 1)$

Constraints: $N <= 5*10^5$

I’m not able to fill the dp array for this recurrence relationship.