NOI '03 P4 - Data Generator - DMOJ: Modern Online Judge

NOI '03 P4 - Data Generator

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

National Olympiad in Informatics, China, 2003

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$ ~N~ in the original problem from $20$ ~20~ to $200\,000$ ~200\,000~.
Change the time required to cross a street to $T_i$ ~T_i~ $(1 \le T_i \le 1\,000\,000\,000)$ ~(1 \le T_i \le 1\,000\,000\,000)~ minutes (where $i$ ~i~ is the street number).
A condition is introduced: the distance between Tyke's house $Y$ ~Y~ and Jerry's house $X$ ~X~ is less than or equal to the distance between Spike's house $Z$ ~Z~ and Jerry's house $X$ ~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$ ~X~, $Y$ ~Y~, and $Z$ ~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$ ~X~, first arriving at Tyke's house $Y$ ~Y~ (because the distance from Tyke's house $Y$ ~Y~ to Jerry's house $X$ ~X~ is less than or equal to the distance between Spike's house $Z$ ~Z~ to Jerry's house $X$ ~X~), and finally arriving at Spike's house $Z$ ~Z~.

Toontown consists of $N$ ~N~ $(3 \le N \le 200\,000)$ ~(3 \le N \le 200\,000)~ houses and $N-1$ ~N-1~ two-way streets connecting the houses. Traveling along the $i$ ~i~-th street requires a time of $T_i$ ~T_i~ $(1 \le T_i \le 1\,000\,000\,000)$ ~(1 \le T_i \le 1\,000\,000\,000)~ minutes. It is guaranteed that there a path will exist between any two houses.

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

Task Description

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

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

$|XY| \le |XZ|$ ~|XY| \le |XZ|~, and
$|XY| + |YZ|$ ~|XY| + |YZ|~ is maximized.

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

Input Specification

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

Output Specification

The output should contain a single integer $T$ ~T~, the maximum possible value for $|XY| + |YZ|$ ~|XY| + |YZ|~.

Sample Input

Sample Output

Problem translated to English by Alex.

Comments

There are no comments at the moment.