Minimum-average-cost subtree that is not necessarily spanning
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 :(