PEG Judge - NOI '03 - Data Generator

National Olympiad in Informatics, China, 2003

Day 2, Problem 1 - Data Generator

While Alex was solving "The Lucky Mouse" from the NOI2003 practice contest, he felt that it was too easy, so he made some changes:

Change the limit of N in the original problem from 20 to 200000.
Change the time required to cross a street to T_i (1 ≤ T_i ≤ 1000000000) minutes (where i is the street number).
A condition is introduced: the distance between Tyke's house Y and Jerry's house X is less than or equal to the distance between Spike's house Z and Jerry's house X. Even still, Alex was able to solve the problem really quickly. So, he decided to create some input data to test his program. He has just created some layouts satisfying these conditions, but to increase the difficulty of the data, he wishes for you to help him determine a set of values for X, Y, and Z, such that the time it takes for Jerry to receive his presents is maximized.

Revised Problem (Note: You do not have to solve this)

Lucky Jerry Mouse's birthday is coming up, and the bulldogs Spike and Tyke would each like to give him a birthday present. To receive the presents, Jerry plans to depart from his house X, first arriving at Tyke's house Y (because the distance from Tyke's house Y to Jerry's house X is less than or equal to the distance between Spike's house Z to Jerry's house X), and finally arriving at Spike's house Z.

Toontown consists of N (3 ≤ N ≤ 200000) houses and N−1 two-way streets connecting the houses. Traveling along the i-th street requires a time of T_i (1 ≤ T_i ≤ 1000000000) minutes. It is guaranteed that there a path will exist between any two houses.

Jerry's house is at location X, Tyke's house is at location Y, and spike's house is at location Z. Please calculate the shortest possible time Jerry needs to spend before receiving his presents.

Task Description

Definition: Let |AB| represent the minimum time it takes to get from house A to house B in Toontown.

Given the layout of Toontown, find values for X, Y, and Z such that:

|XY| ≤ |XZ|, and
|XY| + |YZ| is maximized.

Determine the value of |XY| + |YZ|.

Input Format

The first line of input contains two integers N (3 ≤ N ≤ 200000) and M (M = N−1), representing the total number of houses and streets. Lines 2 through line N will each provide information on one street. Line i+1 will contain integers U_i, V_i, and T_i (1 ≤ U_i, V_i ≤ N, 1 ≤ T_i ≤ 1000000000), indicating that the i-th street connects houses U_i and V_i and takes T_i minutes to traverse.