2445: 阿Q的棒棒糖
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：0
题目描述
阿Q收到了来自WTY的礼物，一个巨大的棒棒糖。这个棒棒糖是由n个糖果和n-1根短棒连接在一起形成的。糖果从1到n标号。阿Q觉得它太大了不够美观，于是决定拆掉一根短棒，把它分成两个小棒棒糖。 阿Q希望拆开之后，两个小棒棒糖的直径之和最大。 阿Q把棒棒糖的直径定义为最远的两个糖直接的距离。
输入
第一行，一个整数n，表示大棒棒糖有n个糖果； 之后n-1行，每行三个整数x,y,z，表示糖果x与糖果y由长度为z的短棒连接；
输出
一行一个整数，表示直径和的最大值。
样例输入 复制
10
2 1 982
3 1 169
4 1 934
5 1 325
6 1 735
7 1 675
8 2 302
9 3 450
10 5 173样例输出 复制
2668 提示
对于30%的数据 N<=2000
对于100%的数据 N<=100000，z<=1000
某人比较厚道，数据保证正常的DFS不会爆栈。