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)$?