Let T be a tree of n nodes in which each edge is associated with a value and a weight that are a real number and a positive integer, respectively. Given two integers wmin and wmax, and two real numbers dmin and dmax, a path P in a tree is feasible if the sum of the edge weights in P is between wmin and wmax, and the ratio of the sum of the edge values in P to the sum of the edge weights in P is between dmin and dmax. In this paper, we first present an O(nlog2n+h)-time algorithm to find all feasible paths in a tree, where h=O(n2) if the output of a path is given by its end-nodes. Then, we present an O(nlog2n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(nlog2n+h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths.
All Science Journal Classification (ASJC) codes