This paper introduces a new network optimization problem named the Star Tree Problem (STP), which deals with two-step service. This problem has a fixed center, while other nodes can be randomly divided into primary and secondary facility locations. Primary nodes together form a star graph by direct assignment with the center. Secondary nodes form some spanning trees, keeping their nearest primary nodes as the root vertices. STP aims to minimize the total edge installation cost by the star and trees. A discrete multi-verse optimizer (DMVO) algorithm is developed to solve the proposed STP, and the numerical experiments are performed on some benchmark problems. Results and statistical analyses of DMVO against the genetic algorithm (GA) and discrete antlion optimizer (DALO) are also presented. Finally, the proposed problem is applied to solve a particular problem for local cable operators and illustrated with realistic data as a case study.