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 Ti (1 ≤ Ti ≤ 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 Ti (1 ≤ Ti ≤ 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.
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|.
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 Ui, Vi, and Ti (1 ≤ Ui, Vi ≤ N, 1 ≤ Ti ≤ 1000000000), indicating that the i-th street connects houses Ui and Vi and takes Ti minutes to traverse.
The output should contain a single integer T, the maximum possible value for |XY| + |YZ|.
4 3 1 2 1 2 3 1 3 4 1
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 17, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3