Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number k >= 0, we consider the following four cut problems: cutting vertices of weight at most or at least k from the tree by deleting some edges such that the remaining part of the graph is still a tree and the total cost of the edges being deleted is minimized or maximized. The MinMstCut problem (cut vertices of weight at most k and minimize the total cost of the edges being deleted) can be solved in linear time and space and the other three problems are NP-hard. In this paper, we design an 0(nl/epsilon)-time 0(l(2)/epsilon + n)-space algorithm for MaxMstCut, and 0(nl(1/epsilon + log n))-time 0(l(2)/epsilon + n)-space algorithms for the other two problems, MinLstCut and MaxLstCut, where n is the number of vertices in the tree, l the number of leaves, and epsilon > 0 the prescribed error bound. (c) 2012 Elsevier B.V. All rights reserved.