There is a graph with 10 levels. On each level there are 1000 vertices. Each vertex may be connected only with a vertex from next level. Each vertex may be connected with 2 vertices. Each vertex has a coefficient and the cost function is calculated on the basis of the coefficients of all connected vertices.
Required to build a tree with maximum cost. The vertices in the tree should be connected only once.
Thus, it's acyclic, directed graph.