Three-Degree-Bounded Maximum Cost Subtree

Problem Statement Chef has become a rich man and now owns the entire road network in the country, which consists of N cities (numbered from 1 to N) and M bidirectional roads. Each road connects two different cities i and j and has a cost C(i,j) - this is the cost paid by the drivers which use this road (and, thus, it is Chef's profit). The road network has the following properties: - it is possib