[NOI2003]数据生成器

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file jerrygen.in Output file jerrygen.out

【题目背景】

小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了,于是对原题做了一些扩展:

  • 将原题的N从20扩展到200000。
  • 将原题经过一条街道需要的时间改为Ti(1 <= Ti <= 1000000000)分钟(i为街道的编号)。
  • 增加了一个条件:小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。

即使这样,他仍然很快地做了出来。于是,小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图,不过为了增大测试数据的难度,他希望你能帮他选取一组X、Y、Z,使老鼠拿到礼物的时间尽可能地大。

【小明扩展的题目(注意,你并不需要解决此题)】

幸福的老鼠Jerry要过生日了,小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发,先到小狗家Y(因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离),再到大狗家Z,将两份礼物取回。 卡通城由N(3 <= N <= 200000)个居住点和N-1条连接居住点的双向街道组成,经过第i条街道需花费Ti(1 <= Ti <= 1000000000)分钟的时间。可以保证,任两个居住点间都存在通路。

不妨设Jerry家在点X,小狗家在点Y,大狗家在点Z。现在,请你计算,Jerry最快需要耗费多长时间才能拿到生日礼物?

【任务描述】

定义:令|AB|表示卡通城中从A点走到B点需要的最少时间。

给出卡通城的地图,找到一组X、Y、Z,使得:

  • |XY|≤|XZ|
  • |XY|+|YZ|最大。

并求出此时|XY|+|YZ|的值。

【输入文件】

输入文件第一行是两个整数N(3 £ N £ 200000)和M(M=N-1),分别表示居住点总数和街道总数。从第2行开始到第N行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、 Ti(1£Ui, Vi £ N,1 £ Ti £ 1000000000),表示街道i连接居住点Ui和Vi,并且经过街道i需花费Ti分钟。

【输出文件】

输出文件仅包含一个整数T,即|XY|+|YZ|的最大值。

【样例输入】

4 3
1 2 1
2 3 1
3 4 1

【样例输出】

4