In a caliphate from the Sahara Dessert there are N city settlements connected via roads so that from each city one can travel to any other city and the route (the sequence of roads) between them is unique. Caravan transports take place between the cities and within a year there are two transports between any pair of cities: one to and one from. The only condition for the transports is that caravans only travel a distance of exactly K roads; as such, there will be pairs of cities (between which the distance is different from K) between which a caravan won't be able to travel. The caliph has decided to set road taxes, so that each caravan traveling between two cities must pay a tax to access that road. At the end of the year the caliph would like to know the total amount collected from taxes for all roads.
Input Data
Input file caravane.in contains
on the first line the number of cities, N.
After that there are N-1 lines
in form x y t, with the meaning
that between cities x and y
there is a road and t is the
value of the tax for the road between x
and y.
Output Data
Output file caravane.out will
contain a single line with a single integer representing the value collected
throughout a one year period in the entire caliphate.
Restrictions
1 < N < 100 000
0 < K < 32
The tax for each road is a positive integer <= 100
The amount collected is an 8 bytes signed integer.
Examples
| caravane.in | caravane.out | Explanation |
|
5 2 |
108 |
The only caravans are between city pairs 1-3, 1-4, 2-5, 3-1, 3-4, 4-1, 4-3 and 5-2 with taxes 9, 15, 14, 9, 16, 15, 16, and respectively 14. The total amount collected is 108. |
Time limit: 0.6 seconds/test
Total available memory: 30 MB, of which 1 MB for the stack.
student Gheroghe Stefan
A.S.E. Bucharest
stefangh@gmail.com