ThreeDegreeBounded Maximum Cost Subtree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese here
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 possible to reach any city from any other city using the existing roads
 any subset S of 10 or more cities contains at least two different cities A and B such that all the paths between A and B have at least one city X (X≠A and X≠B) in common (note that X does not necessarily belong to S)  note that this implies that if the city X were to be removed from the network, then no path would exist anymore between the cities A and B
However, the antimonopoly committee decided that Chef is making too much money and that some restrictions should be imposed. Chef will be allowed to keep a part P of the road network that he chooses, provided that:
 there exists exactly one path from any city in P to any other city in P using only the roads from P (this means that the sets of cities and roads from P form a tree)
 every city from P has at most 3 roads from P adjacent to it
Note that P may consist of any subset of the N cities and any subset of roads connecting these cities, as long as the two restrictions are satisfied. However, Chef doesn't want to simply pick any part P of the road network which satisfies the restrictions. He would like to choose a part P for which the total cost of the roads which belong to P is maximum. Moreover, he would also like to know how many such parts P of maximum total cost exist. Two parts P1 and P2 are considered different if their subsets of cities are different or if their subsets of roads are different.
Input
The first line contains the integer number T denoting the number of test cases. The description of the T test cases follows. The first line of each test case contains the integer numbers N and M. Each of the next M lines contains three spaceseparated integers: i, j and C(i,j), meaning that there is a road between the cities i and j having cost C(i,j).
Output
For each test case print a line containing two numbers: CMAX and CNT32. CMAX is the maximum cost of any part P which satisfies the restrictions imposed by the antimonopoly committee. Let CNT be the total number of different parts P which have maximum cost and satisfy the restrictions. CNT32 is equal to CNT modulo 2^{32} (i.e. we are only interested in the remainder of CNT when divided by 2^{32}).
Constraints
 1 ≤ T ≤ 6
 1 ≤ N ≤ 100
 N1 ≤ M ≤ min(N×(N1)/2, 450)
 1 ≤ i, j ≤ N (i≠j)
 10000 ≤ C(i,j) ≤ 10000
 There exists at most one road connecting each pair of different cities.
Example
Input: 6 6 7 1 3 1 3 5 2 5 1 3 5 2 1 2 4 2 4 6 3 6 5 1 4 4 1 2 0 2 3 0 3 4 0 2 4 0 4 4 1 2 1 2 3 2 3 4 3 2 4 4 8 7 1 2 1 2 3 1 3 4 1 4 5 2 5 6 1 6 7 1 7 8 1 8 7 1 2 1 2 3 1 3 4 1 4 5 3 5 6 1 6 7 1 7 8 1 8 7 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 Output: 11 2 0 17 0 5 4 1 3 3 18 1
Explanation
Example case 1. The maximum cost of a part P which satisfies the restrictions is 11. There are two such maximum cost parts, both of them containing all the cities and the following roads:
 (1,5), (2,5), (2,4), (3,5), (4,6)
 (1,5), (2,4), (3,5), (4,6), (5,6)
Example case 2. All the roads have cost 0, thus the maximum cost of any part P satisfying the restrictions is 0. The 17 different parts are as follows:
 1 part containing 0 cities
 4 parts containing 1 city (1 part for each of the 4 cities)
 4 parts containing 2 cities and the road between them: {1,2}, {2, 3}, {2,4} and {3,4}
 5 parts containing 3 cities:
 cities 1, 2, 3 and the roads (1,2) and (2,3)
 cities 1, 2, 4 and the roads (1,2) and (2,4)
 cities 2, 3, 4 and the roads (2,3) and (3,4)
 cities 2, 3, 4 and the roads (2,3) and (2,4)
 cities 2, 3, 4 and the roads (2,4) and (3,4)
 3 parts containing all the 4 cities and the following roads:
 (1,2), (2,3), (3,4)
 (1,2), (2,3), (2,4)
 (1,2), (2,4), (3,4)
Example case 3. The maximum cost part P which satisfies the restrictions does not contain any of the roads. Thus, there are 5 possible ways of choosing P, consisting of the following sets of cities: {1}, {2}, {3}, {4}, {}.
Example case 4. Chef decides to keep the entire road network, because it satisfies the restrictions and has the maximum total cost among all of its parts.
Example case 5. Chef has 3 choices for the maximum cost part (whose cost is 3):
 it can choose the entire road network
 it can choose the cities 1, 2, 3, 4 and the roads (1,2), (2,3), (3,4)
 it can choose the cities 5, 6, 7, 8 and the roads (5,6), (6,7), (7,8)
Example case 6. Chef chooses the cities 1, 6, 7, 8 and the roads (1,6), (1,7), (1,8).
Author:  mugurelionut 
Tester:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/DEG3MAXT 
Tags  dynamicprogramming, hard, mugurelionut, oct13 
Date Added:  24072013 
Time Limit:  7.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 