Summary: Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number \(k\geq 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 \(O(nl/\epsilon )\)-time \(O(l^{2}/\epsilon +n)\)-space algorithm for MaxMstCut, and \(O(nl(1/\epsilon +\log n))\)-time \(O(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.