Minimum-average-cost subtree that is not necessarily spanning I'm looking for an efficient algorithm for the following problem:

Input: a rooted tree (undirected) with a cost on each edge.  It could be considered directed away from the root (or towards the root).

Output: a subtree from the root that has the minimum average cost per edge.

There are some results for minimum average-cost spanning trees, but in this case the output is not necessarily spanning.

In the tree below, where A is the root of the tree:


The subgraph containing nodes A and B has average cost mean(6) = 6
We can improve on the average cost by including node C to get mean(6, 5) = 5.5.
The optimal subgraph includes nodes A, B, D and E, but not C, to get mean(6, 7, 1) = 4.67


A greedy algorithm would be a depth-first search that appends edges that lower the mean.  But such an algorithm would miss the optimal subgraph, because it wouldn't append the edge to node D with cost 7.
Tried to add this to the comments thread but stack overflow won't let me (new account)

@j_random_hacker I was thinking along similar lines to DP (a recursive algorithm that ran through the subtrees out to the leaves) but I hit a problem - I don't think the problem has an optimal substructure. 

If you consider the graph in the image below, if x=1 then the 30-weight-edge is not part of the optimal solution (100,1,1,1) whereas if x=40 then it is (100,1,1,30). Inclusion of a specific edge in the optimal solution depends upon the weight of edges in completely separate parts of the graph.

I'd actually started writing some code before I realised. My recursive function assumed that given a subtree &amp; the path from root to subtree you could make a decision but this counterexample broke it :(