Finding a length-constrained maximum-density path in a tree

Let T =(V E w )be anundirected and weighted tree with node set V and edge set E, where w (e)
is an edge weight function for e ∈E. The density of a path, say e1 e2 ...,ek ,isdefined as k
i =1 w (ei )/k. The
length of a path is the number of its edges. Given a tree with n edges and a lower bound L where 1 ≤L ≤n, this
paper presents two efficient algorithms for finding a maximum-density path of length at least L in O(nL) time.
One of them is further modified to solve some special cases such as full m-ary trees in O(n) time.