Find the shortest sub-tree with node deletion
This can be solved with dynamic programming.

Define $A[u,v]$ as follows.  Consider all trees obtainable by starting with the subtree rooted at $v$, removing some of the nodes, and making $u$ be the parent of all of the nodes with no parent.  (Or, to put it another way: all of these trees are a subset of the subtree rooted at $u$; they contain $u$ as their root; and every node in them other than $u$ is either $v$ or a descendant of $v$.)  Then $A[u,v]$ is defined to be the length of the minimal-length tree of this sort.

Notice that we have a recursive relationship for $A[u,v]$.  In particular, if $w_1,\dots,w_k$ denote the children of $v$, then we have

$$A[u,v] = \min(d(u,v) + A[v,w_1] + \dots + A[v,w_k], A[u,w_1] + \dots + A[u,w_k]).$$

(Here the first term in the $\min$ corresponds to the case where $v$ is included in the tree, and the second term where $v$ is not included.)

As a result, we can compute all of the $A[u,v]$ values using dynamic programming.  There are at most $O(|V|^2)$ many values to compute, and each one can be computed in $O(k)$ time where $k$ is the maximum degree of the tree, so the total running time is $O(|V|^2 k)$.