Railway#2775
In the country of Olympia, an economic crisis affected the local railway system. After recent reforms, Olympia's railway consists of stations and N-1 tracks connecting these stations. Each station can be directly connected to no more than six other stations. For any pair of different stations, there is exactly one unique way to travel from the first station to the second.
The main problem facing Olympia's railway is thieves who dismantle tracks at night. Thieves can start from any station and move to any other station without restriction, but cannot pass through any station more than once.
The railway management asks you to determine the maximum possible damage (the total length of tracks that can be dismantled) and the number of ways to achieve this.
The program reads an integer (1 \leq N \leq 100{,}000), the number of railway stations, followed by N-1 triples of integers. Each triple contains information about a track: the first two numbers are the station numbers connected by the track, and the third number is the length of the track in kilometers (length does not exceed km).
The program should print two numbers separated by a space: the maximum possible damage (the total length of tracks that thieves can dismantle) and the number of ways to achieve this damage.
Example 1