Finding a maximum-density path in a tree under the weight and length constraints

Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair (valv,wv), where the value valv is a real number and the weight wv is a positive integer. The density of a path P=〈v1,v2,…,vk〉 is defined as . The weight of P, denoted by w(P), is . Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O(wmaxnL)-time algorithm to find a maximum-density path P in T such that wmin⩽w(P)⩽wmax and the length of P is at least L.