Dynamic Programming Problem on Tree

Question

Given a tree $T$ rooted at 1ドル$. Each node might have more than 2 children. You want to create a tree $S$ where each node have 2ドル$ or less children or a binary tree. For each node $u$ in $T$ which had more than 2ドル$ children. Let $D$ be the number of $u$'s children. You can add $D-2$ node to replace the edge connecting $u$ and its children to form a new tree where $u$ is the root and the leaf nodes are its children. There are many possible ways to create $S$. Find the minimum depth of $S$ where depth is the maximum distance from root to some leaves.

My idea is to use Dynamic Programming approach. Let $dp[u]$ be the minimum depth we can make for subtree which $u$ is the root. Let $v$ be the child node of $u$. My approach is to sort $dp[v]$ in descending order and then use Dynamic Programming on the sorted list in $O(n^3)$. Similar to the solution of Matrix Chain Multiplication. But this approach is too slow. Is there any greedy solution so that I can calculate $dp[u]$ in $O(n)$ or $O(n log n)$?

Answer 1

So the difficulty is to determine $dp[u]$, depth of $u$, starting from the list of its sons depths $L[dp[v]]$.

Once $L[dp[v]]$ is sorted in a heap, you can recursively and greedily pop the 2 minimum values $i$, $j$ and push 1ドル+max(i, j)$.

For instance, $L[dp[v]] = [7,5,5,4,3,2,2]$:

=> [7,5,5,4,3,3]
=> [7,5,5,4,4]
=> [7,5,5,5]
=> [7,6,5]
=> [7,7]

$dp[u] = 8$

This is actually $O(nlog(n))$ due to the heap sort.