← 返回题目
题库练习 最远点对
← 上一题 下一题 →

A71441 | 最远点对

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一棵 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)。

输出格式

输出一个整数，代表最远点对之间的距离。

输入输出样例

输入 #1
8
2 1 1
3 2 2
1 4 -3
5 1 5
7 8 8
6 5 -4
7 5 -1
输出 #1
15
输入 #2
3
1 2 -1
1 3 -2
输出 #2
0
C++ 编辑器
输入
输出