  We present linear-time algorithms for partitioning a path or a tree with
weights on the vertices by removing $k$ edges to maximize the minimum-weight
component. We also use the same framework to partition a path with weight on
the vertices, removing $k$ edges to minimize the maximum-weight component. The
algorithms use the parametric search paradigm, testing candidate values until
an optimum is found while simultaneously reducing the running time needed for
each test. For path-partitioning, the algorithm employs a synthetic weighting
scheme that results in a constant fraction reduction in running time after each
test. For tree-partitioning, our dual-pronged strategy makes progress no matter
what the specific structure of our tree is.
