2570 - 最远点对
题目描述
给定一棵 n 个结点的带权树（结点编号1 \sim n），树上的每条边都有一个权值。
请求出该树上的最远点对的路径长度。最远点对的定义是树上任意取 2 个结点，这 2 个结点之间的路径长度最长。
输入
第 1 行有一个整数 n （1≤n≤10^5）。
接下来 n-1 行每行有 3 个整数 x,y,z，表示结点 x 到 结点 y 之间有一条长度为 z 的边。(1≤x,y≤n，x \neq y，-10^4≤z≤10^4)。
输出
输出一个整数，代表最远点对之间的距离。
样例
输入
8 2 1 1 3 2 2 1 4 -3 5 1 5 7 8 8 6 5 -4 7 5 -1
输出
15
输入
3 1 2 -1 1 3 -2
输出
0
说明
【样例 2 解释】
样例 2 中所有边的权值均为负数，可以选择相同的点对，比如选择 1 到 1，也就是自己到自己不移动，得到路径长度为 0 ，也是允许的。
标签
