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(val_v, w_v), where the valueval_v is a real number and the weightw_v is a positive integer. The density of a path P = 〈 v₁, v₂, ..., v_k 〉 is defined as ∑_{i = 1}^k val_i / ∑_{i = 1}^k w_i. The weight of P, denoted by w (P), is ∑_{i = 1}^k w_i. Given a tree of n nodes, two integers w_min and w_max, and a length lower bound L, we present a pseudo-polynomial O (w_max n L)-time algorithm to find a maximum-density path P in T such that w_min ≤ w (P) ≤ w_max and the length of P is at least L.