An exact but somewhat complicated $O(n\log n)$ algorithm
This problem intrigued me, and the solution I've come up with uses a strategy that's totally new to me (I doubt it's new to the world -- if anyone knows of other problems that can be solved "this way", let me know!). This algorithm allows negative and/or fractional edge costs, and operates directly on trees that may be non-binary. To get the time complexity down to $O(n\log n)$ requires making use of a property of averages, as well as a way to efficiently add "blocks" of edges at a time.
Let the input tree be $T$, and the parent of a vertex $v$ be $p(v)$. I will call a subtree of $T$ rooted at some node $v$ and including the edge $p(v)v$ a branch, and say that it is headed by $p(v)v$. (Note that a branch headed by $uv$ need not include all descendants of $v$.) Denote by $A(G)$ the average of all edges in the graph $G$.
Combining averages
Lemma 1: The average of the union of two multisets is between the original two averages.
Proof: Suppose multiset 1 has $b$ items, which sum to $a$, and multiset 2 has $d$ items, which sum to $c$. Then the average of multiset 1 is $a/b$, the average of multiset 2 is $c/d$, and the average of their union is $(a+c)/(b+d)$. We want to show that the last expression is between the first two.
Suppose w.l.o.g. that $a/b \le c/d$. Then:
$$
a/b \le c/d\\
ad \le bc\\
ad+ab \le bc+ab\\
a(b+d) \le b(a+c)\\
a/b \le (a+c)/(b+d)
$$
Similar reasoning shows that $(a+c)/(b+d) \le c/d$.
The utility of this is that it allows us to be certain that adding a multiset to another multiset with a higher average "pulls down" the latter multiset's average, without having to know anything about the items in either multiset or even their sizes.
Stragegy: Greedy, but not using the raw edge costs
The key to enabling a correct greedy algorithm is the following lemma. The statement is rather convoluted, but in essence it means, "Whenever an optimal solution includes some branch, it must also include every branch with a lower average that could have been added to it at some point".
Lemma 2: Suppose there is an optimal solution $OPT$ that contains an edge $uv$. Call the branch in $OPT$ headed by $uv$ $b_{uv}$. Then this optimal solution must also include every edge $xy$ such that $x$ is in $OPT$, is not within the subtree of $T$ rooted at $v$, and there exists a branch $b_{xy}$ in $T$ headed by $xy$ with lower average, i.e., such that $A(b_{xy}) < A(b_{uv})$.
Proof: Suppose (towards contradiction) that an optimal solution $OPT$ does exist that contains some edge $uv$ heading a branch $b_{uv}$, but does not contain some edge $xy$ for which there exists a branch $b_{xy}$ in $T$ such that $A(b_{xy}) < A(b_{uv})$.
Let $r$ be what is left of $OPT$ if we remove $b_{uv}$. It must be that $A(r) \ge A(b_{uv})$, since otherwise we could remove $b_{uv}$, and by Lemma 1 obtain a new solution with strictly lower average, contradicting the optimality of $OPT$. Thus, again by Lemma 1, $A(OPT) = A(r \cup b_{uv}) \ge A(b_{uv})$.
$A(b_{xy}) < A(b_{uv})$ by assumption, and the preceding sentence establishes $A(b_{uv}) \le A(OPT)$, so combining these we have $A(b_{xy}) < A(OPT)$. So by Lemma 1 again, we get that $A(OPT \cup b_{xy}) < A(OPT)$, contradicting the optimality of $OPT$. Thus $xy$ must also be part of this solution.
What this means is that we never need to consider adding an edge to the solution until we have already added every edge that leads to a lower-average branch. IOW, at each step as we are building the solution tree, from among the "frontier" of edges that are adjacent to vertices already in the solution, the only edge we need to consider adding is the one that leads to the subtree having the minimum average. This also makes the stopping criterion clear: Stop as soon as the minimum-attainable-average rises above the average of the solution we have built so far. (Once the minimum is too high to be useful, every other edge surely is too.)
Computing the minimum averages efficiently with "blocks"
So what we need is a way to efficiently compute, for each edge $uv$ in $T$, the minimum average of any branch in $T$ that is headed by $uv$. Once we have these, we can repeatedly pick the lowest-minimum-average edge from a heap, add it to the current solution, and then add all of its child-edges to the heap, continuing until the lowest minimum-average edge exceeds the current solution average.
This is starting to look like a nicer problem: These minimum-average values depend only on the tree below the edge under consideration, suggesting a bottom-up computation might work. It does, but we need to be careful to avoid the time complexity blowing back up to $O(n^2)$.
The straightforward approach would be: For each edge $uv$ in a postorder traversal, create a new solution containing just that edge, add all of the (already-computed) minimum averages of its child edges to a heap, choose the lowest, add it to the solution and add its own child edges to the heap, and repeat until the stopping criterion is met. This is a correct algorithm, but the problem is that it may be necessary to add $O(n)$ edges separately for each starting edge $uv$, leading to $O(n^2)$ time overall. For example this is true of any tree in which every edge costs less than its parent, since in this case the optimal solution for each starting edge $uv$ winds up including every edge in the subtree below it, each of which are added separately.
Instead, once we have discovered all the edges of an optimal branch headed by $uv$, we can collapse all of $v$'s descendants in this branch into $v$, which acquires as children all children of those original vertices. $v$ now represents a solid subtree "block" that is never split apart by later algorithm steps, and which can be added in a single step. (The original subtree structure can be stowed away inside $v$ to enable the top-level solution subtree to be recursively "exploded" back out once the algorithm is finished.)
Exotic heaps to the rescue
An edge is only ever collapsed at most once throughout the course of the whole algorithm, and collapsing an edge can be done in $O(1)$ time, so there are no efficiency concerns there. But there remains the issue of uncollapsed child edges: These may need to be considered for addition into the solution multiple times, potentially once per ancestor. Or do they? The only way we "consider" these edges is by selecting the one having minimum average value among all frontier edges, and a heap can do this in $O(\log n)$ time. So the only remaining issue is ensuring that, when we select an edge to add to the solution and want to add all of its child edges to the heap, this can be done efficiently. This is a heap meld operation, and while it can't be done efficiently by the "standard" binary heap, other heap data structures can accomplish this in as little as $O(1)$ amortised time!
![A graph whose dot code is: digraph G {rankdir="LR"; A -> B [label = "6"]; B -> C [label = "5"]; B -> D [label = "7"]; D -> E [label = "1"];}](https://i.stack.imgur.com/G42Bb.png)
