All submissions for this problem are available.
The Indus Valley civilization was one of the most ancient and advanced civilizations. Amazed by the talent of the people of the time, Google and Facebook decided to travel back in time to set up offices in Indus Valley Civilization. They will set up offices in different cities but there is no further information on the likely location of these offices. Rohan, a prospective employee will need to travel often between these offices and wants to find the expected distance between the two offices.
The network of roads in the city is such that there is a unique path between two cities and hence a unique value for the distance between any two cities. We have also been assured that any two cities are indeed connected to each other.
Input : First line of a test file contains T, the number of test cases. For each test case, the first line is N, the number of cities. This is followed by N-1 lines containing three space seperated integers c1, c2 and l denoting a road from c1 to c2 of length l. It is guranteed that each city is connected to every other city.
Output : For each test case, output the floor of the answer.
1<= T <= 10
1<= N <= 100000
0 <= c1, c2 < N
1 <= l <= 1000
The sum of N over all test cases will not be more than 100000.
Input : 1 4 1 0 1 2 1 1 3 0 1 Output : 1 (floor of 1.6666667)
Explanation : Avg distance = [( d(c0, c1) + d(c0, c2) + d(c0, c3) + d(c1, c2) + d(c1, c3) + d(c2, c3) ) / 6] = [( 1 + 2 + 1 + 1 + 2 + 3)/6] = [10/6] = 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.